LeetCode 3370 - Smallest Number With All Set Bits

The problem asks us to find the smallest integer x such that: 1. x = n 2. Every bit in the binary representation of x is set to 1 A number whose binary representation contains only set bits looks like this: - 1 → binary "1" - 3 → binary "11" - 7 → binary "111" - 15 →…

leetcodeeasymathbit-manipulation

LeetCode Problem 3370

Difficulty: 🟢 Easy
Topics: Math, Bit Manipulation

Solution

Problem Understanding

The problem asks us to find the smallest integer x such that:

  1. x >= n
  2. Every bit in the binary representation of x is set to 1

A number whose binary representation contains only set bits looks like this:

  • 1 → binary "1"
  • 3 → binary "11"
  • 7 → binary "111"
  • 15 → binary "1111"

These numbers follow a very specific mathematical pattern. A number with all bits set can always be written as:

$$2^k - 1$$

For example:

  • $2^1 - 1 = 1$
  • $2^2 - 1 = 3$
  • $2^3 - 1 = 7$
  • $2^4 - 1 = 15$

The input is a single positive integer n, and we must return the smallest number of the form $2^k - 1$ that is greater than or equal to n.

The constraint is:

$$1 \le n \le 1000$$

This is a very small range, which means even a brute force solution would work comfortably. However, the problem is designed to test understanding of bit manipulation patterns and mathematical properties of binary numbers.

There are several important edge cases:

  • n is already a number with all bits set, such as 3 or 7. In this case, we should return n directly.
  • n is just above a power-of-two-minus-one boundary, such as 8. The answer becomes the next all-set-bits number, 15.
  • The minimum value n = 1, which is already valid.
  • Values near the upper limit, such as 1000, where we still need to correctly determine the next valid number.

Approaches

Brute Force Approach

A straightforward approach is to start from n and check every number one by one until we find a number whose binary representation contains only 1s.

To verify whether a number contains only set bits, we can repeatedly inspect each bit using bit operations. If any bit is 0, the number is invalid.

For example, starting from 10:

  • 10 → 1010, invalid
  • 11 → 1011, invalid
  • 12 → 1100, invalid
  • 13 → 1101, invalid
  • 14 → 1110, invalid
  • 15 → 1111, valid

This approach is correct because it eventually checks every number greater than or equal to n, so the first valid number encountered must be the smallest valid answer.

However, this method is inefficient compared to what is possible mathematically. Even though the constraints are small, we can do much better by recognizing the binary pattern.

Optimal Approach

The key observation is that every number containing only set bits has the form:

$$2^k - 1$$

This happens because:

  • $2^k$ in binary is 1 followed by k zeros.
  • Subtracting 1 flips all those zeros into ones.

For example:

$$2^4 = 10000_2$$

$$2^4 - 1 = 1111_2$$

So instead of checking every number individually, we can repeatedly generate numbers of the form:

$$1, 3, 7, 15, 31, ...$$

until we find the first one greater than or equal to n.

We can build these incrementally using the recurrence:

$$x = (x << 1) | 1$$

This shifts all bits left by one position and appends a 1 at the end.

Example progression:

  • 1
  • 11
  • 111
  • 1111

This gives an elegant and efficient solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(answer - n) O(1) Checks each number individually
Optimal O(log n) O(1) Generates only all-set-bit numbers

Algorithm Walkthrough

  1. Initialize a variable current to 1.

This represents the smallest number whose binary representation contains only set bits. 2. Repeatedly check whether current is at least n.

If it is, then we have found the smallest valid answer and can return it immediately. 3. If current is still smaller than n, generate the next all-set-bits number.

We do this using:

$x = (x \ll 1) \mid 1$

The left shift moves every bit one position left, and the bitwise OR with 1 appends a new set bit. 4. Continue until current >= n.

Why it works

The algorithm generates the sequence:

$$1, 3, 7, 15, 31, ...$$

These are exactly all integers whose binary representations contain only 1s. Since the sequence is strictly increasing, the first value that is greater than or equal to n must be the smallest valid answer.

Python Solution

class Solution:
    def smallestNumber(self, n: int) -> int:
        current = 1
        
        while current < n:
            current = (current << 1) | 1
        
        return current

The implementation starts with current = 1, which corresponds to binary "1".

The while loop continues until current becomes large enough to satisfy the condition current >= n.

Inside the loop, we generate the next all-set-bits number using:

current = (current << 1) | 1

Suppose current = 7:

  • Binary representation: 111
  • Left shift: 1110
  • OR with 1: 1111

So the next value becomes 15.

Once the loop terminates, current is guaranteed to be the smallest valid number, so we return it.

Go Solution

func smallestNumber(n int) int {
    current := 1

    for current < n {
        current = (current << 1) | 1
    }

    return current
}

The Go implementation follows exactly the same logic as the Python version.

Go integers support bitwise operations directly, so the expression:

(current << 1) | 1

works identically.

Since the constraint is only up to 1000, there are no integer overflow concerns.

Worked Examples

Example 1

Input:

n = 5
Iteration current Binary current < n
Start 1 1 Yes
1 3 11 Yes
2 7 111 No

Return:

7

Example 2

Input:

n = 10
Iteration current Binary current < n
Start 1 1 Yes
1 3 11 Yes
2 7 111 Yes
3 15 1111 No

Return:

15

Example 3

Input:

n = 3
Iteration current Binary current < n
Start 1 1 Yes
1 3 11 No

Return:

3

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Each iteration increases the number of bits by one
Space O(1) Only a few integer variables are used

The sequence of all-set-bit numbers grows exponentially:

$$1, 3, 7, 15, 31, ...$$

After each iteration, the number roughly doubles. Therefore, the number of iterations needed is proportional to the number of bits in n, which is $O(\log n)$.

The algorithm uses constant extra memory because it only stores one integer variable.

Test Cases

solution = Solution()

assert solution.smallestNumber(1) == 1      # minimum input
assert solution.smallestNumber(2) == 3      # next all-set-bit number
assert solution.smallestNumber(3) == 3      # already valid
assert solution.smallestNumber(4) == 7      # just above previous boundary
assert solution.smallestNumber(5) == 7      # example case
assert solution.smallestNumber(7) == 7      # already all set bits
assert solution.smallestNumber(8) == 15     # power of two
assert solution.smallestNumber(10) == 15    # example case
assert solution.smallestNumber(15) == 15    # already valid
assert solution.smallestNumber(16) == 31    # next boundary
assert solution.smallestNumber(31) == 31    # all bits set
assert solution.smallestNumber(32) == 63    # next all-set-bit number
assert solution.smallestNumber(1000) == 1023  # upper constraint region
Test Why
n = 1 Smallest possible input
n = 2 Requires moving to next valid number
n = 3 Already contains all set bits
n = 4 First number after a valid boundary
n = 5 Provided example
n = 7 Larger already-valid value
n = 8 Exact power of two
n = 10 Provided example
n = 15 Larger all-set-bit number
n = 16 Just above valid boundary
n = 31 Multiple set bits already valid
n = 32 Another power-of-two transition
n = 1000 Near upper constraint

Edge Cases

One important edge case occurs when n is already a valid all-set-bits number, such as 3, 7, or 15. A careless implementation might continue searching unnecessarily and return a larger value. This implementation avoids that issue because the loop stops immediately once current >= n.

Another important case is when n is an exact power of two, such as 8 or 16. Powers of two have binary representations like 1000 or 10000, which contain many zero bits. The correct answer must therefore jump to the next all-set-bits number. The algorithm naturally handles this because the generated sequence progresses directly from 7 to 15, then from 15 to 31.

A third edge case is the smallest possible input, n = 1. Since 1 already consists entirely of set bits, the answer should remain 1. The loop condition while current < n correctly skips all iterations in this case.

Another subtle case involves the upper constraint values, such as 1000. The algorithm must still correctly determine the next valid number, which is 1023 (1111111111 in binary). Because the sequence grows exponentially, only a few iterations are required even for the largest inputs.