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 <= 1000This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Iterative Incremental Approach | Time Complexity: O(n) in worst case where |
| Bit Manipulation - Direct Calculation | Time Complexity: O(1) |
Counting Bits - Dynamic Programming - Leetcode 338 - Python • NeetCode • 159,557 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