algoadvance

Leetcode 191. Number of 1 Bits

Problem Statement

Write a function hammingWeight that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Clarifying Questions

  1. Input Size: What is the range of the input integer?
    • The input is a 32-bit unsigned integer.
  2. Output: What should be the output for an integer with no ‘1’ bits?
    • The output should be 0.
  3. Edge Cases: Do we need to handle negative input values?
    • Since the input is an unsigned integer, there are no negative numbers.

Strategy

We can solve this problem in several ways, but the most straightforward method is to iterate through each bit of the number and count the number of ‘1’ bits.

Steps:

  1. Initialize a count to 0.
  2. Iterate through all 32 bits of the integer.
  3. For each bit, check if it is ‘1’:
    • Perform a bitwise AND operation with 1.
    • If the result is 1, increment the count.
  4. Right shift the integer by one position.
  5. Repeat steps 3 and 4 until all bits have been checked.
  6. Return the count.

Code

#include <iostream>

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n != 0) {
            count += (n & 1);  // Increment count if the last bit is 1
            n >>= 1;           // Right shift n by 1 
        }
        return count;
    }
};

int main() {
    Solution sol;
    uint32_t n = 11;  // Example input: binary representation of 11 is 1011
    std::cout << "Number of 1 bits: " << sol.hammingWeight(n) << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(1) because the number of iterations is fixed (32 times) for a 32-bit integer. Each operation inside the loop is constant time.

Space Complexity

The space complexity is O(1) as we are only using a few integer variables for counting and bit manipulation without any additional data structures.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI