LeetCode 3370: Smallest Number With All Set Bits – Problem Explanation and Solutions

Are you looking to master bit manipulation and tackle interesting coding challenges? In this post, we’ll explore LeetCode Problem 3370: Smallest Number With All Set Bits. We’ll dive deep into the problem statement, break down a brute force approach, and finally discuss an optimized solution.

If you’re preparing for technical interviews or just love solving algorithmic problems, this guide is for you!

Problem Statement: Smallest Number With All Set Bits

You are given a positive integer n. Your task is to find the smallest number x such that:

• x is greater than or equal to n.
• The binary representation of x consists only of set bits (1s).

Examples:

• Example 1:
  Input: n = 5
  Output: 7
  Explanation:
  The binary representation of 7 is 111, which is the smallest number greater than or equal to 5 with all bits set.

• Example 2:
  Input: n = 10
  Output: 15
  Explanation:
  The binary representation of 15 is 1111.

• Example 3:
  Input: n = 3
  Output: 3
  Explanation:
  The binary representation of 3 is already 11, so it remains the same.

Constraints:

• 1 <= n <= 1000

---

Approach 1: Brute Force Solution

The brute force method builds the smallest number with all set bits by iterating through the bits of n.

Code Implementation (C++):

class Solution {

    public:

        int smallestNumber(int n) {

            int num = 0;

            int i = 0;

            while (n) {

                num = num | (1 << i); // Set the ith bit in num

                i++;

                n = n >> 1;           // Right shift n to process the next bit

            }

            return num;

        }

    };

   

Explanation:

1. Initialize num to 0 and a bit position i to 0.
2. Iterate through the bits of n. For each bit:
   • Set the corresponding bit in num using the bitwise OR (|) operation.
   • Increment the bit position i.
   • Right shift n to move to the next bit.
3. Once all bits have been processed, return num.

Example Walkthrough:

• For n = 5 (binary 101):
  • Set the 0th bit: num = 1.
  • Set the 1st bit: num = 3 (11 in binary).
  • Set the 2nd bit: num = 7 (111 in binary).
• Result: 7.

Time Complexity:

• O(log n): The loop runs in proportion to the number of bits in n.
• Space Complexity: O(1), as we use only a few variables.

---

Approach 2: Optimized Solution

A more efficient solution leverages the concept of finding the most significant bit (MSB) and setting all bits up to that position.

Code Implementation (C++):

class Solution {

    public:

        int smallestNumber(int n) {

            int msb = 31 - __builtin_clz(n);

            return (1 << (msb + 1)) - 1;     // Set all bits up to that position

        }

    };

   

Explanation:

1. Find the MSB:
   Use the built-in function __builtin_clz(n) to count leading zeros. The MSB position is 31 - __builtin_clz(n).
2. Set all bits:
   Shift 1 left by (msb + 1) positions and subtract 1 to get a number with all bits set.

Example Walkthrough:

• For n = 10 (binary 1010):
  • MSB is at position 3.
  • (1 << 4) - 1 = 16 - 1 = 15 (1111 in binary).
• Result: 15.

Time Complexity:

• O(1): All operations are constant-time bit manipulations.
• Space Complexity: O(1).

---

Why Bit Manipulation is Key

Bit manipulation allows you to solve problems like this efficiently. Instead of looping through numbers, you directly construct the result using shifts and bitwise operations.

Key Takeaways:

• Use brute force if constraints are small.
• For larger inputs, always look for patterns or shortcuts using bit manipulation.

FAQs (Frequently Asked Questions)

1. What does "all set bits" mean?

It means the binary representation of the number consists only of 1s (e.g., 111, 1111).

2. Why does the brute force method work?

It sets every bit position encountered in n, ensuring the smallest number with all bits set.

3. What is the significance of __builtin_clz?

It counts leading zeros, helping find the highest set bit efficiently.

4. Can this problem be solved without bit manipulation?

Yes, but bit manipulation provides the most optimized solution.

5. What is the time complexity of the brute force approach?

O(log n), as it processes each bit of n.

6. How does the optimized approach achieve O(1) time?

It uses direct bit operations without loops.

7. What if n is already a number with all set bits?

The function returns n itself (e.g., n = 3 → 11).

8. Does this problem have real-world applications?

Yes, in binary encoding, error detection, and compression algorithms.

9. Can this be extended to larger numbers beyond 1000?

Yes, but ensure integer limits are respected (e.g., 1 << 31 may overflow).

10. How can I practice more bit manipulation problems?

Try LeetCode problems like:

• 191. Number of 1 Bits
• 231. Power of Two
• 268. Missing Number

---

Bit manipulation is a must-know topic for coding interviews. This problem demonstrates how a simple observation can lead to an optimal solution. Practice more bitwise problems to strengthen your understanding!

🔹 Got a question? Drop it in the comments!
🔹 Want more coding breakdowns? Subscribe for updates!

#BitManipulation #LeetCode #CodingInterview #Algorithms #Programming

---