grid47 Exploring patterns and algorithms
Sep 20, 2024
5 min read
Solution to LeetCode 477: Total Hamming Distance Problem
The Hamming distance between two integers is the number of positions at which the corresponding bits differ. Given an integer array nums, return the sum of Hamming distances between all pairs of integers in nums.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `nums`.
Example: nums = [3, 10, 5]
Constraints:
• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^9
Output: Return the sum of Hamming distances between all pairs of integers in `nums`.
Example: Output: 8
Constraints:
• The answer will fit in a 32-bit integer.
Goal: Calculate the total Hamming distance between all pairs of integers in the array.
Steps:
• 1. Loop through each bit position (from 0 to 31, as numbers are within the 32-bit range).
• 2. For each bit position, count how many numbers have that bit set (1).
• 3. For each bit position, the total number of differing bits is `bitCount * (n - bitCount)`, where `n` is the size of the array and `bitCount` is the number of 1s in the current bit position.
• 4. Sum up the contributions from all bit positions.
Goal: The constraints involve the length of the array and the values of the integers.
Steps:
• The length of `nums` is between 1 and 10^4.
• Each integer in `nums` is between 0 and 10^9.
Assumptions:
• The values in `nums` are non-negative integers.
• Input: nums = [3, 10, 5]
• Explanation: The binary representations of 3, 10, and 5 are compared bit by bit to calculate the Hamming distances between all pairs.
• Input: nums = [2, 3, 2]
• Explanation: In this case, the binary representations of 2, 3, and 2 are used to calculate the Hamming distances.
Approach: The approach involves calculating the Hamming distance by iterating through each bit position and counting how many numbers have a 1 at each position.
Observations:
• The problem is a bitwise problem, which makes it suitable for bit manipulation techniques.
• By considering each bit position separately, we can efficiently calculate the total Hamming distance.
• We can process each bit independently to determine how many numbers have differing bits in that position.
Steps:
• 1. Iterate over all 32 bit positions.
• 2. For each bit position, count how many numbers have a 1 at that position.
• 3. Compute the contribution to the total Hamming distance using the formula `bitCount * (n - bitCount)`.
• 4. Sum the results from all bit positions.
Empty Inputs:
• There will always be at least one element in the array, as per the constraints.
Large Inputs:
• The solution needs to handle large arrays of size up to 10^4 efficiently.
Special Values:
• If all numbers in `nums` are the same, the Hamming distance between any pair will be 0.
Constraints:
• The solution must work within the constraints, where the array size is up to 10^4 and the numbers can be as large as 10^9.
inttotalHammingDistance(vector<int>& nums) {
int total =0, n = nums.size();
for(int i =0; i <32; i++) {
int bitCnt =0;
for(int j =0; j < nums.size(); j++)
bitCnt += (nums[j] >> i) &1;
total += bitCnt * (n - bitCnt);
}
return total;
}
1 : Function Definition
inttotalHammingDistance(vector<int>& nums) {
Defines the `totalHammingDistance` function that takes a vector of integers `nums` and calculates the total Hamming distance between all pairs of integers.
2 : Variable Initialization
int total =0, n = nums.size();
Initializes two variables: `total` to accumulate the total Hamming distance, and `n` to store the size of the `nums` vector.
3 : Bit Manipulation
for(int i =0; i <32; i++) {
Begins a loop that iterates over all 32 bits (assuming 32-bit integers) to calculate the Hamming distance for each bit position.
4 : Variable Initialization
int bitCnt =0;
Initializes the `bitCnt` variable to count how many numbers have a `1` at the current bit position `i`.
5 : Bitwise Operation
for(int j =0; j < nums.size(); j++)
Begins a loop that iterates through each number in the `nums` vector.
6 : Bitwise Operation
bitCnt += (nums[j] >> i) &1;
Performs a bitwise right shift on `nums[j]` to examine the `i`th bit. If the bit is `1`, increments `bitCnt`.
7 : Accumulation
total += bitCnt * (n - bitCnt);
Updates the `total` by adding the number of differing bits between pairs. For each bit, the number of differing bits is the product of `bitCnt` and `(n - bitCnt)`.
8 : Return Statement
return total;
Returns the total Hamming distance.
Best Case: O(n * 32)
Average Case: O(n * 32)
Worst Case: O(n * 32)
Description: The time complexity is O(n * 32), where n is the size of the `nums` array, and 32 is the number of bits to consider.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since the solution uses only a few variables to track the bit counts.
