题目描述
给你两个整数 n
和 x
。你需要构造一个长度为 n
的 正整数 数组 nums
,对于所有 0 <= i < n - 1
,满足 nums[i + 1]
大于 nums[i]
,并且数组 nums
中所有元素的按位 AND 运算结果为 x
。
返回 nums[n - 1]
可能的 最小 值。
样例
输入:n = 3, x = 4
输出:6
解释:
数组 nums 可以是 [4,5,6],最后一个元素为 6。
输入:n = 2, x = 7
输出:15
解释:
数组 nums 可以是 [7,15],最后一个元素为 15。
限制
1 <= n, x <= 10^8
算法
(思维题,位运算) $O(\log n)$
- 注意到,数组中最小的数字一定是 $x$,且之后每个数字,都是在 $x$ 的基础上,按顺序降 $x$ 中二进制为 $0$ 的数位变为 $1$。
- 例如,如果 $x$ 是 $4$,则第一个数字为 $(100)_2$,第二个数字为 $(101)_2$,第三个数字为 $(110)_2$,第四个数字为 $(111)_2$,第五个数字为 $(1100)_2$,依次类推。
- 除去第一个数字外,需要快速找到 $n - 1$ 个比 $x$ 大的数字。借鉴快速幂的思想,将 $n - 1$ 进行二进制分解,假设分解后位置 $k$ 的值为 $1$,则把 $x$ 的第 $k$ 个 $0$ 的位置变为 $1$。
- 定位 $x$ 中 $0$ 的位置,可以通过将 $x$ 取反,然后使用 lowbit 的方式快速求出。
时间复杂度
- 二进制分解 $n$,时间复杂度为 $O(\log n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
public:
LL minEnd(int n, int x) {
--n;
LL ans = x, t = ~x;
int i = 0;
while (n) {
if (n & 1)
ans |= t & -t;
n >>= 1;
t -= t & -t;
}
return ans;
}
};