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
Example 1:
Input: n = 5
Output: 7
Explanation:
The binary representation of 7 is "111".
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 "11".
Constraints:
1 <= n <= 1000Problem Overview: You are given an integer n. The task is to return the smallest number greater than or equal to n whose binary representation consists entirely of set bits (all 1s). Numbers like 1 (1), 3 (11), 7 (111), and 15 (1111) satisfy this property.
Approach 1: Iterative Incremental Approach (Time: O(ans - n), Space: O(1))
Start from n and keep incrementing the value until you find a number whose binary representation contains only set bits. A useful bit trick identifies such numbers: a value with all bits set satisfies x & (x + 1) == 0. This works because numbers like 111...111 become a power of two when incremented, which clears all lower bits. Iterate until the condition holds, then return that number. This approach is straightforward and easy to reason about, though in the worst case you may check several numbers before reaching the next valid one.
Approach 2: Bit Manipulation - Direct Calculation (Time: O(1), Space: O(1))
All numbers with every bit set follow the pattern 2^k - 1. The goal is to find the smallest such value that is greater than or equal to n. Observe that 2^k - 1 ≥ n when k ≥ ceil(log2(n + 1)). Compute k from the bit length of n, then return (1 << k) - 1. This avoids iteration entirely and directly constructs the correct number using bit shifts. The approach relies on patterns in binary representation and is a classic use of bit manipulation combined with simple math reasoning.
Recommended for interviews: The direct bit manipulation approach is what most interviewers expect. It demonstrates recognition of the 2^k - 1 pattern and comfort with binary operations. The iterative approach still helps show understanding of the property x & (x + 1) == 0, which is a common trick in bit manipulation problems.
This approach involves incrementing the number n until we find a number whose binary representation consists only of set bits (1s). The key observation here is that numbers like 3, 7, 15, etc., have all their bits set.
In the C solution, we start with x = n and increment x until the expression (x & (x + 1)) == 0 is true, which means all bits in x are set.
Time Complexity: O(n) in worst case where x needs many increments
Space Complexity: O(1) as no extra space is used.
Instead of incrementing, this approach calculates the number directly using bit manipulation. The idea is to find the bit-length of n and return a number of all ones of that bit-length.
We find the number of bits required to represent n and generate a number with all bits of that length set.
Time Complexity: O(1)
Space Complexity: O(1)
We start with x = 1 and continuously left shift x until x - 1 geq n. At this point, x - 1 is the answer we are looking for.
The time complexity is O(log n), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Incremental Approach | Time Complexity: O(n) in worst case where |
| Bit Manipulation - Direct Calculation | Time Complexity: O(1) |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Incremental Approach | O(ans - n) | O(1) | Good for understanding the bit property x & (x + 1) == 0 and for quick brute-force style reasoning. |
| Bit Manipulation - Direct Calculation | O(1) | O(1) | Best for interviews and production code. Uses the 2^k - 1 pattern to compute the answer instantly. |
Smallest Number With All Set Bits - Leetcode 3370 - Python • NeetCodeIO • 6,167 views views
Watch 9 more video solutions →Practice Smallest Number With All Set Bits with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor