Sum the Bit Differences across All Array Pairs
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Sum the Bit Differences across All Array Pairs
The Hamming distance between two nonnegative integers is the number of bit positions at which their binary representations differ, with leading zeros supplied as needed.
Given `nums`, return the sum of these distances over every unordered pair of distinct indices. Each pair `i < j` contributes once. Equal values at different indices are still separate array entries.
### Interface
`class Solution { public: int totalHammingDistance(vector<int>& nums); };`
### Example 1
```text
Input: nums = [1,2,3]
Output: 4
```
The relevant binary forms are `01`, `10` and `11`. The three pair distances are 2, 1 and 1, totaling 4.
### Example 2
```text
Input: nums = [0,0,7]
Output: 6
```
The two zeros have distance 0. Each zero has distance 3 from 7, so both occurrences together contribute 6.
### Constraints
- `1 <= nums.length <= 10000`.
- `0 <= nums[i] <= 1000000000`.
- The answer fits in a signed 32-bit integer.
### What a Strong Answer Covers
- Counting unordered index pairs exactly once, including repeated values.
- Single-element arrays and arrays of identical values.
- A correctness argument for the total and resource bounds at the full input size.
- Safe intermediate arithmetic before returning an `int`.
```hint Separate contributions
Consider how much a single bit position contributes to the total.
```
Overview: Sum Hamming distances over unordered pairs of array indices, including repeated values, within the original nonnegative integer bounds.