Show problems as
Classic problem #477MediumArrayMathBit Manipulation

Total Hamming Distance

Real-world version: Differing Flag Bits Across Registers
Tracked in this browser only
Read Total Hamming Distance on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Every unit on a shop floor publishes its state as one non-negative integer whose binary digits act as independent flags. Line up the binary forms of two states, padding the shorter one with leading zeros so both have the same width. Their disagreement is how many bit positions hold a 1 in exactly one of the two states.

You are handed registers, the current state of each unit in reporting order. Add up the disagreement of every unordered pair of two different positions in registers and return that total. Two units holding the same state still form a pair; their disagreement is 0.

A list with a single unit has no pairs at all.

Examples

Example 1

Input
registers = [6, 11, 20, 3]
Output
17

Written to five bit positions the four states are 00110, 01011, 10100 and 00011. The six pairs disagree in 3, 2, 2, 5, 1 and 4 positions respectively, and those add up to the returned total.

Example 2

Input
registers = [9, 9, 24]
Output
4

The first two states are identical, so that pair disagrees nowhere. State 9 is 01001 and state 24 is 11000, which disagree in 2 positions, and that pair occurs twice.

Example 3

Input
registers = [7, 7, 7, 7]
Output
0

All four units publish the same state, so every one of the six pairs disagrees nowhere.

Constraints

  • 1 <= registers.length <= 10^4
  • 0 <= registers[i] <= 10^9
  • Under these bounds the returned total is at most 10^9.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def total_flag_disagreement(registers: list[int]) -> int:
Java
public int totalFlagDisagreement(int[] registers)

More on the same topics