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

 

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;
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn smallest_number(n: i32) -> i32 {
        let mut x = 1;
        while x - 1 < n {
            x <<= 1;
        }
        x - 1
    }
}

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

Comments