What is the main strategy to solve the Minimum Array End problem?

The strategy involves using bitwise operations to construct an array where the AND of all elements equals a given value x, while ensuring the array is strictly increasing.

How does bit manipulation factor into the Minimum Array End problem?

Bit manipulation is essential to ensure the bitwise AND of the array elements equals the target value x. Elements are constructed by merging x with incrementing values.

What is the time complexity of the Minimum Array End problem?

The time complexity is O(log n), where n is the number of elements, due to the bitwise manipulation required to solve the problem.

What is the role of the last element in the Minimum Array End problem?

The last element of the array is the key to minimizing the output while still satisfying the bitwise AND condition across all elements.

Can the strategy used in the Minimum Array End problem apply to other bitwise problems?

Yes, the strategy of merging values using bitwise operations is a common technique used in other bitwise manipulation problems to minimize or meet specific constraints.

#3133

Medium

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

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

给你两个整数 n 和 x 。你需要构造一个长度为 n 的正整数数组 nums ，对于所有 0 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。返回 nums[n - 1] 可能的最小值。示例 1：输入： n = 3…

位运算

题目描述

给你两个整数 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⁸

lightbulb

解题思路

方法一：贪心 + 位运算

根据题目描述，要使得数组的最后一个元素尽可能小，且数组中的元素按位与的结果为 $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

11

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

speed

复杂度分析

指标	值
时间	O(\log n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of bitwise operations and their application in problem-solving.
question_mark
Evaluates the candidate’s ability to construct an array with constraints using bit manipulation.
question_mark
Assesses knowledge of optimization techniques when dealing with bitwise AND operations.

warning

常见陷阱

外企场景

error
Not properly understanding the bitwise AND operation and how it impacts the selection of elements.
error
Incorrectly merging values without ensuring that the array remains strictly increasing.
error
Failing to minimize the last element while maintaining the required bitwise AND condition.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the number of elements in the array and observe how the merging process scales.
arrow_right_alt
Modify the bitwise AND condition to use a different value and test for edge cases.
arrow_right_alt
Introduce additional constraints on the array elements, such as limits on individual values or their bitwise characteristics.

help

常见问题

外企场景

继续练习

#3145 大数组元素的乘积 #3117 划分数组得到最小的值之和 #3149 找出分数最低的排列