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

🟠   🔖  位运算  🔗 力扣 LeetCode

题目

You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i + 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.

Return the minimum possible value of nums[n - 1].

Example 1:

Input: n = 3, x = 4

Output: 6

Explanation:

nums can be [4,5,6] and its last element is 6.

Example 2:

Input: n = 2, x = 7

Output: 15

Explanation:

nums can be [7,15] and its last element is 15.

Constraints:

• 1 <= n, x <= 10^8

题目大意

给你两个整数 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 <= 10^8

解题思路

1. BigInt 处理大数：

   • 为了确保算法能处理极大的输入（如 n = 10^8），需要将 n 和 x 转换为 BigInt 类型，以避免溢出。

2. 循环遍历位掩码：

   • 使用一个位掩码 mask 从 1n（即二进制最低位）开始，每次左移一位，遍历所有位。
   • 对于每一位，检查 x 的当前位是否为 0。如果 x 在该位为 0，则可以尝试在 number 中设置这一位，以确保最后生成的数不影响最终 AND 的结果。

3. 按条件更新 number：

   • 对于每一位：
     • 检查 x 的当前位，如果它为 0，则考虑是否将该位设为 1，使得生成的数尽可能大。
     • 为此，使用 (n & 1n) * BigInt(mask)，这在 n 的最低位为 1 时会将 number 的相应位设为 1。
     • 然后将 n 右移一位，以检查下一位。
   • 这样做的结果是，只在 n 指定的某些位置将 number 设为更高的值。

4. 转换并返回结果：

   • 将最终得到的 number 转换为 Number 类型并返回。

复杂度分析

• 时间复杂度：O(log n)，因为每次循环中 n 右移一位。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number} n
 * @param {number} x
 * @return {number}
 */
var minEnd = function (n, x) {
	var number = BigInt(x);
	n = BigInt(n) - 1n;
	for (var mask = 1n; n > 0n; mask <<= 1n) {
		if ((mask & BigInt(x)) == 0n) {
			number = number | ((n & 1n) * BigInt(mask));
			n >>= 1n;
		}
	}
	return Number(number);
};