跳转至

3133. 数组最后一个元素的最小值

题目描述

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

返回 nums[n - 1] 可能的 最小 值。

 

示例 1：

输入：n = 3, x = 4

输出：6

解释：

数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

示例 2：

输入：n = 2, x = 7

输出：15

解释：

数组 nums 可以是 [7,15] ，最后一个元素为 15 。

 

提示：

  • 1 <= n, x <= 108

解法

方法一：贪心 + 位运算

根据题目描述，要使得数组的最后一个元素尽可能小，且数组中的元素按位与的结果为 \(x\)，那么数组的第一个元素必须为 \(x\)。

假设 \(x\) 的二进制表示为 \(\underline{1}00\underline{1}00\)，那么数组序列为 \(\underline{1}00\underline{1}00\), \(\underline{1}00\underline{1}01\), \(\underline{1}00\underline{1}10\), \(\underline{1}00\underline{1}11\)...

如果我们忽略掉下划线部分，那么数组序列为 \(0000\), \(0001\), \(0010\), \(0011\)...，第一项为 \(0\)，那么第 \(n\) 项为 \(n-1\)。

因此，答案就是在 \(x\) 的基础上，将 \(n-1\) 的二进制的每一位依次填入 \(x\) 的二进制中的 \(0\) 位。

时间复杂度 \(O(\log x)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        ans = x
        for i in range(31):
            if x >> i & 1 ^ 1:
                ans |= (n & 1) << i
                n >>= 1
        ans |= n << 31
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public long minEnd(int n, int x) {
        --n;
        long ans = x;
        for (int i = 0; i < 31; ++i) {
            if ((x >> i & 1) == 0) {
                ans |= (n & 1) << i;
                n >>= 1;
            }
        }
        ans |= (long) n << 31;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    long long minEnd(int n, int x) {
        --n;
        long long ans = x;
        for (int i = 0; i < 31; ++i) {
            if (x >> i & 1 ^ 1) {
                ans |= (n & 1) << i;
                n >>= 1;
            }
        }
        ans |= (1LL * n) << 31;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func minEnd(n int, x int) (ans int64) {
    n--
    ans = int64(x)
    for i := 0; i < 31; i++ {
        if x>>i&1 == 0 {
            ans |= int64((n & 1) << i)
            n >>= 1
        }
    }
    ans |= int64(n) << 31
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function minEnd(n: number, x: number): number {
    --n;
    let ans: bigint = BigInt(x);
    for (let i = 0; i < 31; ++i) {
        if (((x >> i) & 1) ^ 1) {
            ans |= BigInt(n & 1) << BigInt(i);
            n >>= 1;
        }
    }
    ans |= BigInt(n) << BigInt(31);
    return Number(ans);
}

评论