Sum of Bit Differences

Medium

For two non-negative integers, call their *difference* the number of positions in binary where their bits disagree. For example, 4 (100) and 7 (111) have a difference of 2. Given an array values, return the sum of differences over all pairs of elements; each unordered pair of distinct positions counts once. Checking every pair is O(n²); try to do better.

Example 1

values=[5, 3, 6] → 6

5 = 101, 3 = 011, 6 = 110. The pairs 5/3, 5/6 and 3/6 each differ in 2 bits, 6 in total.

Example 2

values=[8, 8, 0] → 2

The two 8s match (0), and each differs from 0 in one bit: 0 + 1 + 1 = 2.

Example 3

values=[7] → 0

Constraints

1 ≤ len(values) ≤ 10⁴
0 ≤ values[i] ≤ 10⁹
The answer is less than 2³¹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Math

Similar problems

Eight Lamps After Many Nights Medium Split Into Equal-XOR Halves Medium Take From Any Pile Medium Switch Lines to Darken the Board Medium Fewest Lines Through the Dots Medium

Input

values=[5, 3, 6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 86 tests on the server, hidden ones included.