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

1
2
3
4

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

Example 2

1
2
3
4

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

Example 3

1
2
3
4

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

1
2
3
4
5
6
7
8
9

#include <cmath>
class Solution {
public:
    int smallestAllSetBits(int n) {
        int k = 1;
        while ((1 << k) - 1 < n) ++k;
        return (1 << k) - 1;
    }
};
1
2
3
4
5
6
7

class Solution {
    public int smallestAllSetBits(int n) {
        int k = 1;
        while ((1 << k) - 1 < n) k++;
        return (1 << k) - 1;
    }
}
1
2
3
4
5
6

class Solution:
    def smallestAllSetBits(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.