Number Of 1 Bits Leetcode Problem 191 [Python Solution]

Welcome back, coding enthusiasts!

In this blog post, we are going to explore the Number Of 1 Bits problem, which is categorized as an easy problem in LeetCode’s Blind 75 list.

If you’ve been following our Blind 75 journey, you’ll know that we’ve been tackling these problems one by one.

If you’re interested in the full list, you can find it here.

The objective of this problem is to write a function that takes an unsigned integer’s binary representation and calculates the number of ‘1’ bits it contains.

This concept is also known as “Hamming weight.” Before we dive into the problem, let’s clarify a few key points:

1. In some programming languages, such as Java, there is no explicit unsigned integer type.

However, in practice, this doesn’t affect our implementation, as the binary representation remains the same whether the integer is signed or unsigned.

Java compilers represent signed integers using 2’s complement notation.

Now, let’s proceed with an example to understand the problem better.

Problem Overview

Example 1:

Input: n = 00000000000000000000000000001011

Output: 3

Explanation: The input binary string 00000000000000000000000000001011 contains a total of three ‘1’ bits.

To solve this problem, we will employ a bit manipulation approach.

Specifically, we will present two solutions.

The first solution is relatively straightforward, while the second one, though more efficient, is slightly more complex.

Understanding Constraints

Before we dive into the solutions, let’s briefly understand the constraints of the problem:

• The input must be a binary string of length 32. Now, let’s explore the first solution, which is more accessible for beginners.

Example 1 – Python Code Solution

def hammingWeight(self, n: int) -> int:
    result = 0
    while n:
        result += n & 1
        n >>= 1
    return result

In this Python code solution, we start by initializing a variable result to keep track of the total number of ‘1’ bits.

We use a while loop that continues as long as n is not equal to zero.

To identify whether the rightmost bit of n is ‘1’ or ‘0, we use the n & 1 operation.

If it’s ‘1’, we increment result by one.

We then shift all the bits of n to the right by one, effectively removing the rightmost bit.

The loop continues to check each bit of the binary representation until n becomes zero, and the final count of ‘1’ bits is returned as the result.

Time and Space Complexity

Now, let’s discuss the time and space complexity of this solution:

• Time Complexity: O(32) = O(1) since the loop runs a constant number of times (32 bits for a 32-bit integer).
• Space Complexity: O(1) as we are using a fixed amount of extra space.

Reasoning Behind This Approach

The approach we discussed is based on a straightforward bit manipulation technique.

We start with the rightmost bit and check if it’s ‘1’ or ‘0, incrementing the count accordingly.

Then, we shift the bits to the right to process the next bit.

This continues until we’ve examined all the bits in the binary representation.

The use of bit manipulation allows us to efficiently count the ‘1’ bits in the binary string without the need for string conversion or complex arithmetic.

An Efficient Approach with Bit Manipulation

Now, let’s delve into a more efficient approach that leverages a bit manipulation trick.

This technique allows us to count the ‘1’ bits directly, reducing the number of iterations.

Efficient Python Code Solution

def hammingWeight(self, n: int) -> int:
    result = 0
    while n:
        n &= n - 1
        result += 1
    return result

In this efficient Python code solution, we start with a similar setup as the previous solution.

We initialize result to track the ‘1’ bits and utilize a while loop that continues as long as n is not zero.

The key to this efficient approach lies in the line n &= n - 1.

This operation is the heart of the optimization.

Here’s how it works:

1. We take the current value of n.
2. We subtract 1 from it (n - 1).
3. We perform a bitwise AND operation between the original n and the result of n - 1.

The result of this operation is that it clears the rightmost ‘1’ bit in n while leaving all other bits unchanged.

This effectively eliminates one ‘1’ bit from the count without the need for examining each bit individually.

We then increment the result by 1 to keep track of the ‘1’ bits removed in each iteration.

The loop continues until n becomes zero, and the final count of ‘1’ bits is returned as the result.

Related Interview Questions By Company:

• Number Of 1 Bits LeetCode
• Missing Number LeetCode
• Balanced Binary Tree LeetCode

Related Interview Questions By Difficulty:

• Counting Bits LeetCode
• Single Number LeetCode
• Reverse Bits LeetCode

Related Interview Questions By Category:

• Maximum Product Subarray LeetCode
• Decode String LeetCode
• Sort An Array LeetCode

Conclusion

In this blog post, we’ve explored the Number Of 1 Bits problem from LeetCode, providing two Python solutions.

The first solution employs a straightforward approach of checking each bit one by one, while the second solution utilizes a bit manipulation trick to efficiently count the ‘1’ bits.

It’s essential for beginners to understand both solutions, as they highlight the fundamental concept of bit manipulation, which is valuable for various coding challenges.

The efficient approach, although slightly more complex to grasp, showcases the power of clever bit manipulation techniques in algorithm optimization.

As you continue your coding journey, don’t hesitate to experiment with these solutions, practice your bit manipulation skills, and explore more LeetCode problems.

If you found this blog post helpful, please like, engage, and share your thoughts and questions in the comments.

Your feedback and engagement are highly encouraged, and they contribute to the growth of our coding community.

Now, as you venture into the world of coding, keep challenging yourself, asking questions, and never stop learning.

Happy coding!

LeetCode Problem Link