跳转至

3370. 仅含置位位的最小整数

题目描述

给你一个正整数 n。

返回 大于等于 n 且二进制表示仅包含 置位 位的 最小 整数 x 。

置位 位指的是二进制表示中值为 1 的位。

 

示例 1：

输入： n = 5

输出： 7

解释：

7 的二进制表示是 "111"。

示例 2：

输入： n = 10

输出： 15

解释：

15 的二进制表示是 "1111"。

示例 3：

输入： n = 3

输出： 3

解释：

3 的二进制表示是 "11"。

 

提示：

  • 1 <= n <= 1000

解法

方法一：位运算

我们从 $x = 1$ 开始，不断将 $x$ 左移，直到 $x - 1 \geq n$，此时 $x - 1$ 就是我们要找的答案。

时间复杂度 $O(\log n)$，空间复杂度 $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;
}

评论