Problem: We have N integers. The i-th integer is A_i.  Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \mbox{ XOR } A_j), modulo (10^9+7).  What is \mbox{ XOR }?  The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:    * When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.  For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Submission attempts (in order):
def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  
  
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = (a & (2**i) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1
      else:
        ones[i] += 1

  
  xs = []
  i = 0
  while True:
    x_i = 0
    if i <= 59:
      x_i = (zeros[i] * ones[i])
    if i >= 1:
      x_i += xs[i - 1] // 2
    xs.append(x_i)

    if i >= 60 and x_i // 2 == 0:
      break

    i += 1

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))


def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  
  
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      a_bin = format(a, '060b')
      a_i_digit_from_right = a_bin[60 - i - 1]
      if a_i_digit_from_right == '0':
        zeros[i] += 1
      else:
        ones[i] += 1

  
  xs = []
  i = 0
  while True:
    x_i = 0
    if i <= 59:
      x_i = (zeros[i] * ones[i])
    if i >= 1:
      x_i += xs[i - 1] // 2
    xs.append(x_i)

    if i >= 60 and x_i // 2 == 0:
      break

    i += 1

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


# n = int(input().strip())
# a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))


def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  def get_ret_from_xs2(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * x
      ret %= 10**9 + 7
    return ret

  
  
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = ((a & (2**i)) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1
      else:
        ones[i] += 1

  
  xs = [zeros[i] * ones[i] for i in range(60)]
  return get_ret_from_xs2(xs)


  
  # xs = []
  
  # while True:
  #   x_i = 0
  
  #     x_i = (zeros[i] * ones[i])
  
  #     x_i += xs[i - 1] // 2
  #   xs.append(x_i)
  #
  #   if i >= 60 and x_i // 2 == 0:
  #     break
  #
  

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


# n = int(input().strip())
# a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))


def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  def get_ret_from_xs2(xs: List[int]) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * x
      ret %= 10**9 + 7
    return ret

  
  
  zeros = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      # a_bin = format(a, '060b')
      # a_i_digit_from_right = a_bin[60 - i - 1]
      # if a_i_digit_from_right == '0':
      
      # else:
      #   ones[i] += 1

      a_i_digit_from_right = ((a & (2**i)) >> i) & 0b1
      if a_i_digit_from_right == 0:
        zeros[i] += 1

  
  xs = [zeros[i] * (len(a_s) - zeros[i]) for i in range(60)]
  return get_ret_from_xs2(xs)


  
  # xs = []
  
  # while True:
  #   x_i = 0
  
  #     x_i = (zeros[i] * ones[i])
  
  #     x_i += xs[i - 1] // 2
  #   xs.append(x_i)
  #
  #   if i >= 60 and x_i // 2 == 0:
  #     break
  #
  

  #xs = [2, 3, 1]
  #return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))



def solve(a_s) -> int:
  def get_ret_from_xs(xs) -> int:
    ret = 0
    for i, x in enumerate(xs):
      ret += 2**i * (x % 2)
      ret %= 10**9 + 7
    return ret

  
  
  zeros = [0] * 60
  ones = [0] * 60

  for a in a_s:
    for i in range(len(zeros)):
      a_bin = format(a, '060b')
      a_i_digit_from_right = a_bin[60 - i - 1]
      if a_i_digit_from_right == '0':
        zeros[i] += 1
      else:
        ones[i] += 1

  xs = []

  for i in range(len(zeros)):
    x_i = (zeros[i] * ones[i]) % 10**9 + 7
    if i >= 1:
      x_i += xs[i - 1] // 2
    xs.append(x_i)

  #xs = [2, 3, 1]
  return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))


def solve(a_s) -> int:
  # def get_ret_from_xs(xs) -> int:
  
  
  #   for i, x in enumerate(xs):
  
  
  #   return ret
  #
  # def get_ret_from_xs2(xs) -> int:
  
  #   for i, x in enumerate(xs):
  
  
  #   return ret

  
  
  zeros = [0] * 60

  ret = 0
  for i in range(60):
    ones = sum([(a >> i) & 0b1 for a in a_s])
    ret += 2**i * (ones * (len(a_s) - ones))
    ret %= 10**9 + 7
  return ret

  # for a in a_s:
  
  #     # a_bin = format(a, '060b')
  #     # a_i_digit_from_right = a_bin[60 - i - 1]
  #     # if a_i_digit_from_right == '0':
  
  #     # else:
  #     #   ones[i] += 1
  #
  #     a_i_digit_from_right = (a >> i) & 0b1
  #     if a_i_digit_from_right == 0:
  
  #
  
  
  # return get_ret_from_xs2(xs)
  #
  #
  
  # # xs = []
  
  # # while True:
  # #   x_i = 0
  
  # #     x_i = (zeros[i] * ones[i])
  
  # #     x_i += xs[i - 1] // 2
  # #   xs.append(x_i)
  # #
  # #   if i >= 60 and x_i // 2 == 0:
  # #     break
  # #
  
  #
  # #xs = [2, 3, 1]
  # #return get_ret_from_xs(xs)


n = int(input().strip())
a_s = [int(s) for s in input().split()]

#a_s = [1, 2, 3]
#a_s = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
#a_s = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

print(solve(a_s))


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted