grid47 Exploring patterns and algorithms
Oct 18, 2024
4 min read
Solution to LeetCode 191: Number of 1 Bits Problem
Given a positive integer n, return the number of set bits (1s) in its binary representation, also known as the Hamming weight.
Problem
Approach
Steps
Complexity
Input: The input consists of a positive integer n.
Example: n = 9
Constraints:
• The integer n is between 1 and 2^31 - 1.
Output: The output is the number of set bits (1s) in the binary representation of the integer n.
Example: Output = 2
Constraints:
• The output is a single integer representing the number of set bits.
Goal: The goal is to count the number of set bits in the binary representation of the integer n.
Steps:
• Step 1: Use bitwise operations to efficiently count the number of set bits.
• Step 2: Continuously remove the lowest set bit from n and increment the count until n becomes zero.
• Step 3: Return the count of set bits.
Goal: The problem constraints ensure that the input n is a valid positive integer.
Steps:
• n is between 1 and 2^31 - 1.
Assumptions:
• The input integer is always a positive number within the specified range.
• Input: Input: n = 9
• Explanation: The binary representation of 9 is 1001, which has two set bits, so the output is 2.
Approach: We can solve this problem using bitwise operations to count the number of set bits in the integer's binary representation.
Observations:
• We can use a bitwise trick to remove the lowest set bit of the number and count how many times this operation can be performed.
• By using n = n & (n - 1), we can eliminate the rightmost set bit in each iteration until all bits are processed.
Steps:
• Step 1: Initialize a count variable to store the number of set bits.
• Step 2: Iterate over the integer and repeatedly remove the lowest set bit using the operation n = n & (n - 1).
• Step 3: Increment the count in each iteration.
• Step 4: Return the final count after the loop ends.
Empty Inputs:
• The input is always a valid positive integer, so there are no empty inputs.
Large Inputs:
• Since n is constrained between 1 and 2^31 - 1, large inputs are not an issue.
Special Values:
• If n is a power of 2 (e.g., 1, 2, 4, 8, 16, ...), the binary representation will have only one set bit.
Constraints:
• The input is always a positive integer.
inthammingWeight(uint32_t n) {
int key =0;
while(n) {
n = n & (n -1);
key++;
}
return key;
}
1 : Function Definition
inthammingWeight(uint32_t n) {
Define the function 'hammingWeight' that takes a 32-bit unsigned integer 'n' and returns the count of 1 bits in its binary representation.
2 : Variable Initialization
int key =0;
Initialize a variable 'key' to zero, which will be used to count the number of 1 bits in the binary representation of 'n'.
3 : Loop Iteration
while(n) {
Start a while loop that continues until 'n' becomes zero. The loop iterates through each 1 bit in 'n'.
4 : Bitwise Operation
n = n & (n -1);
Apply the bitwise AND operation between 'n' and 'n-1'. This operation clears the least significant 1 bit in 'n'.
5 : Count Increment
key++;
Increment the 'key' variable to count the number of 1 bits encountered so far.
6 : Return Statement
return key;
Return the final count of 1 bits stored in 'key'.
Best Case: O(1)
Average Case: O(k), where k is the number of set bits in n.
Worst Case: O(32), in the worst case when all bits are set to 1.
Description: The time complexity is O(k), where k is the number of set bits, because we process each set bit individually. In the worst case, k is at most 32.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1), as we only need a constant amount of space for the count variable.
