Smallest Number With All Set Bits

Problem

You are given a positive number n.

Return the smallest number x greater than or equal to n, such that the binary representation of x contains only set bits

Examples

Example 1

Input: 5
Output: 7
Explanation:
The binary representation of 7 is `"111"`.

Example 2

Input: 10
Output: 15
Explanation:
The binary representation of 15 is `"1111"`.

Example 3

Input: 3
Output: 3
Explanation:
The binary representation of 3 is `"11"`.

Constraints

• 1 <= n <= 1000

Solution

Method 1 – Bit Manipulation: Next All-Set-Bits Number

Intuition

The smallest number with all set bits (i.e., of the form 2^k - 1) that is greater than or equal to n can be found by finding the smallest k such that (2^k - 1) >= n.

Approach

1. Start with k = 1 and compute (2^k - 1).
2. Increment k until (2^k - 1) >= n.
3. Return (2^k - 1).

Code

C++

#include <cmath>
class Solution {
public:
    int smallestNumber(int n) {
        int k = 1;
        while ((1 << k) - 1 < n) ++k;
        return (1 << k) - 1;
    }
};

Java

class Solution {
    public int smallestNumber(int n) {
        int k = 1;
        while ((1 << k) - 1 < n) k++;
        return (1 << k) - 1;
    }
}

Python

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

Complexity

• ⏰ Time complexity: O(log n) — Each step doubles the value, so at most log n steps.
• 🧺 Space complexity: O(1) — Only a few variables are used.