Welcome to Subscribe On Youtube
3370. Smallest Number With All Set Bits
Description
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
Solutions
Solution 1: Bit Manipulation
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)$.
-
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 - 1 -
func smallestNumber(n int) int { x := 1 for x-1 < n { x <<= 1 } return x - 1 } -
function smallestNumber(n: number): number { let x = 1; while (x - 1 < n) { x <<= 1; } return x - 1; }