Bit Manipulation - Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given an integer array nums, return the sum of Hamming distances between all the pairs of the integers in nums.

Input: nums = [4, 14, 2]
Output: 6
Explanation: Hamming distances: (4,14)=2, (4,2)=2, (14,2)=2. Total = 6.

Input: nums = [4, 14, 4]
Output: 4
Explanation: Hamming distances: (4,14)=2, (4,4)=0, (14,4)=2. Total = 4.

For each bit position, count how many numbers have that bit set (call it ones) and how many have it unset (zeros = n - ones). The contribution of this bit position to the total Hamming distance is ones * zeros. Sum across all 32 bit positions.

For each of the 32 bit positions, count the number of 1-bits (ones) among all nums.
The zeros count is n - ones.
Each pair with one number having a 1 and the other a 0 contributes 1 to the Hamming distance.
Add ones * zeros to total for each bit position.

class Solution { public int totalHammingDistance(int[] nums) { int total = 0; int n = nums.length; for (int i = 0; i < 32; i++) { int ones = 0; for (int num : nums) { ones += (num >> i) & 1; } total += ones * (n - ones); } return total; } }

Complexity Analysis:

Time complexity: O(32 * n) = O(n) — 32 bit positions each with n iterations.
Space complexity: O(1) — constant extra space.