Fleet-Wide Bit Drift

MediumBit Manipulation

Problem

Each device in a fleet reports a configuration word in configs. The drift between two devices is the number of bit positions where their words differ.

Return the total drift summed over every unordered pair of devices.

Example 1

Input:
configs = [4, 14, 2]
Output:
6

drift(4, 14) = 2, drift(4, 2) = 2, drift(14, 2) = 2.

Example 2

Input:
configs = [1, 2, 3]
Output:
4

Constraints

  • 1 ≤ configs.length ≤ 10^4
  • 0 ≤ configs[i] < 2^31
  • The answer fits in a 32-bit signed integer.

Hint

Show the first hint

Comparing every pair is O(n²). Can you count each bit position's contribution separately?

Walkthrough

How to approach it

01Clarify before coding

  • Ordered or unordered pairs? Unordered: (a, b) and (b, a) count once.
  • Can the answer overflow? With n = 10^4 and 31 bits the maximum is 31 · 2.5 · 10^7 = 7.75 · 10^8, which fits.

02Brute force

For every pair, popcount the XOR of the two words and add it up.

Cost: O(n² · 31) time: about 1.5 · 10^9 bit operations at n = 10^4. Too slow.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.