How do you solve Number of 1 Bits on LeetCode?

Number of 1 Bits (LeetCode #191) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(1) space complexity. Key insight: Understanding bit manipulation can lead to more efficient solutions.

What is the brute force solution for Number of 1 Bits?

The brute force approach for Number of 1 Bits is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves converting the number to its binary representation and counting the number of '1's. It's straightforward but not the most efficient way to solve the problem. The optimal Optimal Solution approach improves this to O(log n).

What algorithm or data structure is used to solve Number of 1 Bits?

Number of 1 Bits uses the following concepts: Divide and Conquer, Bit Manipulation. The recommended patterns to study are: Bit Manipulation, Counting Bits.

What are the interview tips for Number of 1 Bits?

Always consider both brute-force and optimized solutions during interviews. Explain your thought process clearly, especially when transitioning from brute-force to optimal. Practice bit manipulation problems to become more comfortable with them.

What are common mistakes when solving Number of 1 Bits?

Confusing the number of bits with the value of the number. Not considering edge cases, such as the smallest and largest values of n.

#191

Number of 1 Bits

Easy

Divide and ConquerBit ManipulationBit ManipulationCounting Bits

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(1)	O(1)

💡

Intuition

Time O(log n)Space O(1)

The optimal solution uses bit manipulation to count the set bits directly without converting to a string. This is much faster and more efficient, especially for large numbers.

⚙️

Algorithm

3 steps

1Step 1: Initialize a count variable to 0.
2Step 2: While n is greater than 0, perform the following: - Increment the count if the least significant bit (LSB) is 1 (n & 1). - Right shift n by 1 (n >>= 1).
3Step 3: Return the count.

solution.py8 lines

1# Full working Python code
2
3def hammingWeight(n):
4    count = 0
5    while n:
6        count += n & 1
7        n >>= 1
8    return count

ℹ

Complexity note: The time complexity is O(log n) because we are effectively dividing n by 2 each time (right shift), which reduces the number of bits we need to check.

1Understanding bit manipulation can lead to more efficient solutions.
2Counting bits directly avoids unnecessary conversions and is faster.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.