3370. Smallest Number With All Set Bits

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

Solution:

1 - 1

11 - 3

111 - 7

1111 - 15

\(2^i - 1 \geq n\)

class Solution {
    public int smallestNumber(int n) {
        int i = 1;
        while (true){
            int x = (1 << i) - 1;     // 1 << i = 2^i
            // num >> i   == num / 2^i 下取整
            if (x >= n){
                return x;
            }
            i++;
        }
    }
}

// TC: O(logn)
// SC: O(1)

n = 101

​ 111

长度就是i

class Solution {
    public int smallestNumber(int n) {
        return (1 << Integer.toBinaryString(n).length()) - 1;
    }
}
// TC: O(1)
// SC: O(1)

class Solution {
    public int smallestNumber(int n) {
        String cur = Integer.toBinaryString(n);

        char[] curChar = cur.toCharArray();
        for (int i = 0; i < curChar.length; i++){
            if (curChar[i] != '1'){
                curChar[i] = '1';
            }
        }

        String resultString = new String(curChar);

        return Integer.parseInt(resultString, 2);

    }
}

// TC: O(n)
// SC: O(n)

class Solution {
    public int smallestNumber(int n) {
        int result = 1;
        while(n != 0){
            n = n >> 1;
            result = result * 2;
        }
        return result - 1;
    }
}

// TC: O(n)
// SC: O(1)