Total Hamming Distance Across an Array

Given an array of N non-negative integers, compute the sum of the Hamming distances between every unordered pair of elements, where the Hamming distance between two integers is the number of bit positions at which their binary representations differ. Print the total across all C(N, 2) pairs. The total can exceed the range of a 32-bit integer, so print it using a 64-bit type.

Input: The first line contains the integer N. The second line contains N space-separated non-negative integers, the array elements. Output: A single integer (fits in a 64-bit type): the total Hamming distance summed over every pair.

2 <= N <= 100000; 0 <= arr[i] <= 2^30 - 1 (1073741823)

This 'analyze each bit position's contribution independently, then sum across positions' technique is a broadly reusable pattern whenever a problem asks for something aggregated ACROSS PAIRS but can be decomposed bit-by-bit - it converts an O(N²) problem into an O(N * bits) one.

Sum the Hamming distance (number of differing bits) between every pair of numbers in an array. Brute force: Compute the Hamming distance for every pair directly (comparing full numbers bit by bit) - this costs O(N² * bits), far too slow for N up to 100,000. Optimised: Reframing the problem from 'compare every PAIR' to 'analyze every BIT POSITION independently' transforms an O(N²) pairwise comparison into an O(N * bits) counting problem - for each bit position, a simple count of how many numbers have it set directly gives the exact contribution of that position to the total, via the c*(N-c) formula.

1. Instead of comparing every PAIR directly, consider ONE BIT POSITION at a time. 2. For a given bit position, if exactly c of the N numbers have that bit SET, then exactly c * (N - c) pairs DIFFER at that position (each of the c 'set' numbers pairs with each of the N-c 'unset' numbers). 3. Sum c * (N - c) across all 30 bit positions, using a 64-bit accumulator since the total can exceed 32-bit range.

Time: O(N * B), where B is the number of bit positions (about 30 here) - a linear pass per bit position. Space: O(1) extra space beyond a running count per bit position and the 64-bit total accumulator.

All elements identical gives a total of 0; the maximum possible per-bit contribution occurs when a bit is set in exactly half of the elements.

Be ready to derive the c*(N-c) formula clearly: it counts every (set, unset) PAIR at that bit position exactly once, which is exactly what contributes 1 to that pair's Hamming distance at this specific bit.