algoadvance

Leetcode 191. Number of 1 Bits

Problem Statement

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

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Clarifying Questions

  1. Input Format: Is the input guaranteed to be a 32-bit unsigned integer?
    • Yes, the input is a 32-bit unsigned integer.
  2. Output Format: Should the function return the count as an integer?
    • Yes, the function should return an integer representing the number of ‘1’ bits.
  3. Edge Cases: Are there any specific edge cases to be aware of?
    • The edge case would be the number 0 which has zero ‘1’ bits.

Code

Here’s the Java code to solve the problem:

public class Solution {
    // Function to count the number of 1 bits
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += (n & 1); // increment count if the least significant bit is 1
            n = n >>> 1; // unsigned right shift operator
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int n1 = 0b00000000000000000000000000001011; // Binary literal for ease of testing
        int n2 = 0b00000000000000000000000010000000;
        int n3 = 0b11111111111111111111111111111101;

        System.out.println(sol.hammingWeight(n1)); // Output: 3
        System.out.println(sol.hammingWeight(n2)); // Output: 1
        System.out.println(sol.hammingWeight(n3)); // Output: 31
    }
}

Strategy

  1. Initialize a Counter: Initialize a counter variable to keep track of the number of ‘1’ bits.
  2. Bitwise Operations: Use bitwise operations to check each bit of the input integer.
    • (n & 1) isolates the least significant bit. If it’s 1, we increment the counter.
    • Use unsigned right shift (>>>) to discard the least significant bit each time.
  3. Loop Until Zero: Continue shifting and counting until the input number becomes zero.

Time Complexity

The time complexity of the provided solution is O(1).

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