3133：数组最后一个元素的最小值（1934 分）

力扣第 395 场周赛第 3 题

题目

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

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

示例 1：

示例 2：

提示：

• 1 <= n, x <= 108

分析

• 考虑元素的二进制位，x 二进制为 1 的位数集合 A 是所有元素的交集
• 去掉位数集合 A，剩下的位数拼成的数，等价于从 0 到 n-1
• 因此将 n-1 的二进制填入 A 以外的空即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        n -= 1
        i = 0
        for j in range(n.bit_length()):
            while x>>i&1:
                i += 1 
            x |= (n>>j&1)<<i
            i += 1
        return x

36 ms