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.

---