Smallest Number With All Set Bits
EasyPrompt
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 <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every number starting from n until we find one whose binary representation consists solely of set bits (1s).
Algorithm
- Start a loop with a variable
xinitialized ton. - In each iteration, check if
xis a number with all bits set. A numberyhas all its bits set if it is of the form2^k - 1. A clever bitwise trick to check this condition is(y & (y + 1)) == 0. - If the condition is met, we have found our smallest number
x >= nand we return it. - If the condition is not met, we increment
xby 1 and continue the loop.
Walkthrough
We start a loop with a variable x initialized to n. In each iteration, we check if x is a number with all bits set. A number y has all its bits set if it is of the form 2^k - 1. A clever bitwise trick to check this condition is (y & (y + 1)) == 0. This works because adding 1 to a number composed of all 1s (like ...0111) results in a number that is a power of two (...1000), and the bitwise AND of these two numbers will be zero. If the condition is met, we have found our smallest number x >= n and we return it. If the condition is not met, we increment x by 1 and continue the loop. The loop is guaranteed to terminate because the sequence of numbers with all set bits is infinite (1, 3, 7, 15, ...), so we will eventually find one.
class Solution { public int smallestNumberWithAllSetBits(int n) { int x = n; while (true) { // A number has all set bits if (x & (x + 1)) == 0 // Example: x = 7 (0111), x + 1 = 8 (1000). 7 & 8 = 0. // This check is valid for x > 0. if ((x & (x + 1)) == 0) { return x; } x++; } }}Complexity
Time
O(M - n), where `M` is the smallest number with all set bits that is greater than or equal to `n`. In the worst case, `n` could be `2^k`, and `M` would be `2^(k+1) - 1`. The number of iterations would be `2^k - 1`, which is roughly `n`. So, the complexity is approximately O(n).
Space
O(1), as we only use a constant amount of extra space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient for large
n, especially whennis just slightly larger than a number with all set bits (e.g.,n = 2^k). The number of iterations can be proportional ton.
Instead of checking every number from n upwards, we can generate only the numbers that have all set bits and find the first one that is greater than or equal to n.
Algorithm
- The numbers with all set bits follow a pattern: 1, 3, 7, 15, etc.
- Each subsequent number
c_nextcan be generated from the previous onec_prevbyc_next = (c_prev << 1) | 1. - Start with a
candidate = 1. - In a loop, while
candidate < n, update the candidate to the next number in the sequence. - When the loop terminates,
candidatewill be the smallest number with all set bits that is greater than or equal ton.
Walkthrough
The numbers with all set bits follow a clear pattern: 1 (binary 1), 3 (binary 11), 7 (binary 111), 15 (binary 1111), and so on. Each subsequent number in this sequence can be generated from the previous one. If c is a number with all set bits, the next one is (c * 2) + 1, or using bitwise operations, (c << 1) | 1. The algorithm starts with the first number in the sequence, candidate = 1. It then enters a loop, and in each iteration, it checks if the candidate is less than n. If candidate < n, it generates the next number in the sequence: candidate = (candidate << 1) | 1. The loop continues until candidate is no longer less than n. At this point, candidate is the smallest number with all set bits that is greater than or equal to n. Finally, we return the candidate.
class Solution { public int smallestNumberWithAllSetBits(int n) { // Start with the first number with all set bits, which is 1. long candidate = 1; // Keep generating the next number with all set bits // until it is greater than or equal to n. while (candidate < n) { // The next number is generated by shifting left by 1 and setting the new LSB. // e.g., from 7 (111) to 15 (1111) candidate = (candidate << 1) | 1; } return (int)candidate; }}Complexity
Time
O(log n). The number of iterations is equal to the number of bits in the final result. Since the result is the smallest number of the form `2^k-1` greater than or equal to `n`, its number of bits `k` is proportional to `log n`.
Space
O(1). We only use a single variable to store the candidate.
Trade-offs
Pros
Very efficient, with logarithmic time complexity.
Cons
Requires recognizing the pattern of the target numbers.
This is the most efficient approach. It directly calculates the result by determining the required number of bits and constructing the number in a single step.
Algorithm
- The goal is to find the smallest number
xof the form2^k - 1such thatx >= n. - Let
bbe the number of bits in the binary representation ofn. - The smallest number with all set bits that is
>= nmust have at leastbbits. - The smallest number with
bbits that are all set is2^b - 1. - This number
2^b - 1is also the largest number withbbits, son <= 2^b - 1is always true. - Therefore, the answer is always
2^b - 1. - The algorithm is:
- Find the number of bits,
b, inn. - Calculate and return
(1 << b) - 1.
- Find the number of bits,
Walkthrough
The problem asks for the smallest number x of the form 2^k - 1 such that x >= n. Let's analyze the relationship between n and the result x. If n has b bits in its binary representation, the smallest number with all b bits set is 2^b - 1. Any number with fewer than b bits will be smaller than n (since n's most significant bit is at position b-1). The number 2^b - 1 is the largest possible number with b bits. Therefore, n <= 2^b - 1. This means the smallest number with all set bits that is greater than or equal to n must have at least b bits. The smallest such number is exactly 2^b - 1. So, the algorithm simplifies to these steps:
- Find the number of bits,
b, in the binary representation ofn. - The result is
(1 << b) - 1. The number of bits can be found efficiently. For a 32-bit integer,32 - Integer.numberOfLeadingZeros(n)gives the bit length. Alternatively, a simple loop that repeatedly right-shiftsnuntil it becomes zero can count the bits.
class Solution { public int smallestNumberWithAllSetBits(int n) { // Find the number of bits in n. // For n=5 (101), bits=3. For n=10 (1010), bits=4. int bits = 0; int temp = n; while (temp > 0) { temp >>= 1; bits++; } // The result is a number with 'bits' number of 1s. // This can be calculated as (1 << bits) - 1. // For bits=3, (1 << 3) - 1 = 8 - 1 = 7 (111). // For bits=4, (1 << 4) - 1 = 16 - 1 = 15 (1111). return (1 << bits) - 1; }}Complexity
Time
O(log n) for the loop-based bit counting. If using a hardware instruction like `clz` (count leading zeros), which `Integer.numberOfLeadingZeros` often maps to, the complexity is effectively O(1).
Space
O(1).
Trade-offs
Pros
Most efficient and elegant solution.
Directly computes the answer without iteration or searching.
Cons
Might be slightly less intuitive than the constructive generation approach for beginners.
Solutions
Solution
class Solution {public int smallestNumber(int n) { int x = 1; while (x - 1 < n) { x <<= 1; } return x - 1; }}class Solution {public: int smallestNumber(int n) { int x = 1; while (x - 1 < n) { x <<= 1; } return x - 1; }};class Solution: def smallestNumber(self, n: int) -> int: x = 1 while x - 1 < n: x <<= 1 return x - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.