跳转至

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

来源第 426 场周赛 Q1难度简单分数1198

题目描述

给你一个正整数 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

解法

方法一：位运算

思考

求不小于 \(n\) 的最小「全 \(1\)」二进制数，即形如 \(2^p-1\)。\(n \le 1000\)，左移找最小的 \(2^p>n\) 即可。

从 \(x=1\) 不断左移，直到 \(x-1 \ge n\)，此时 \(x-1\) 的每一位都是 \(1\)。

我们从 \(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;
}

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

评论