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 <= 1000In #3370 Smallest Number With All Set Bits, the key observation comes from understanding how numbers with all bits set look in binary. Such numbers follow a recognizable pattern: 1, 11, 111, 1111, and so on. In decimal form, these correspond to values like 1, 3, 7, 15, which can be expressed as 2^k - 1.
The goal is to determine the smallest value of this pattern that is greater than or equal to the given integer. A useful strategy is to analyze the number of bits required to represent the input and then determine the next valid "all-set-bits" number with that bit length or greater. Bit manipulation or logarithmic reasoning can help quickly identify the correct candidate.
Because the computation relies on simple bit-length calculations, the algorithm runs in constant time and uses O(1) additional space, making it very efficient for interview scenarios.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit-length / Power-of-two minus one observation | O(1) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Find the strictly greater power of 2, and subtract 1 from it.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
A binary number with k bits all set to 1 equals the sum of powers of two from 2^0 to 2^(k-1). This sum equals 2^k - 1, which explains why numbers like 1, 3, 7, and 15 appear when all bits are set.
Problems involving bit manipulation patterns are common in technical interviews at companies like FAANG. While this exact problem may vary, recognizing patterns like 2^k - 1 and reasoning about bit lengths is a frequently tested skill.
No special data structure is required for this problem. It mainly involves bit manipulation and mathematical observations about binary representations, so simple integer operations are sufficient.
The optimal approach relies on recognizing that numbers with all bits set follow the pattern 2^k - 1. By determining the minimum bit length needed for the input number, you can compute the smallest such value that is greater than or equal to n. This allows the problem to be solved in constant time.