Skip to content

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.

A set bit refers to a bit in the binary representation of a number that has a value of 1.

 

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)$.

1
2
3
4
5
6
class Solution:
    def smallestNumber(self, n: int) -> int:
        x = 1
        while x - 1 < n:
            x <<= 1
        return x - 1

1
2
3
4
5
6
7
8
9
class Solution {
    public int smallestNumber(int n) {
        int x = 1;
        while (x - 1 < n) {
            x <<= 1;
        }
        return x - 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int smallestNumber(int n) {
        int x = 1;
        while (x - 1 < n) {
            x <<= 1;
        }
        return x - 1;
    }
};

1
2
3
4
5
6
7
func smallestNumber(n int) int {
    x := 1
    for x-1 < n {
        x <<= 1
    }
    return x - 1
}

1
2
3
4
5
6
7
function smallestNumber(n: number): number {
    let x = 1;
    while (x - 1 < n) {
        x <<= 1;
    }
    return x - 1;
}

Comments