What does 'Construct the Minimum Bitwise Array II' mean in practice?

It means generating an array where each element OR its increment equals the corresponding nums[i], while keeping values as small as possible.

Can ans[i] be negative?

Yes, in some cases minimizing ans[i] to satisfy the OR condition may produce negative values for small nums[i].

Is there a direct formula for ans[i]?

No universal formula exists; each ans[i] depends on the binary pattern of nums[i] and requires bitwise analysis.

What is the role of binary representation in this problem?

Binary representation shows which bits must be set or unset, guiding the minimal construction of ans[i] for the OR condition.

Can this approach be applied to arrays with non-prime numbers?

Yes, but the pattern of minimal ans[i] values may differ and require careful handling of bitwise constraints.

#3315

Medium

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

构造最小位运算数组 II

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下条件均成立： ans[i] OR (ans[i] + 1) == nums[i] 除此以外，你需要最小化结果数组里每一个 ans[i] 。如果没法找到符合条件的 an…

数组位运算

题目描述

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下条件均成立：

ans[i] OR (ans[i] + 1) == nums[i]

除此以外，你需要 最小化 结果数组里每一个 ans[i] 。

如果没法找到符合条件的 ans[i] ，那么 ans[i] = -1 。

质数指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

示例 1：

输入：nums = [2,3,5,7]

输出：[-1,1,4,3]

解释：

对于 i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。
对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。
对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。
对于 i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。

示例 2：

输入：nums = [11,13,31]

输出：[9,12,15]

解释：

对于 i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。
对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。
对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。

提示：

1 <= nums.length <= 100
2 <= nums[i] <= 10⁹
nums[i] 是一个质数。

lightbulb

解题思路

方法一：位运算

对于一个整数 $a$ ，满足 $a \lor (a + 1)$ 的结果一定为奇数，因此，如果 $\text{nums[i]}$ 是偶数，那么 $\text{ans}[i]$ 一定不存在，直接返回 $-1$ 。本题中 $\textit{nums}[i]$ 是质数，判断是否是偶数，只需要判断是否等于 $2$ 即可。

如果 $\text{nums[i]}$ 是奇数，假设 $\text{nums[i]} = \text{0b1101101}$ ，由于 $a \lor (a + 1) = \text{nums[i]}$ ，等价于将 $a$ 的最后一个为 $0$ 的二进制位变为 $1$ 。那么求解 $a$ ，就等价于将 $\text{nums[i]}$ 的最后一个 $0$ 的下一位 $1$ 变为 $0$ 。我们只需要从低位（下标为 $1$ ）开始遍历，找到第一个为 $0$ 的二进制位，如果是第 $i$ 位，那么我们就将 $\text{nums[i]}$ 的第 $i - 1$ 位变为 $1$ ，即 $\text{ans}[i] = \text{nums[i]} \oplus 2^{i - 1}$ 。

遍历所有的 $\text{nums[i]}$ ，即可得到答案。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 $\text{nums}$ 的长度和数组中的最大值。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        ans = []
        for x in nums:
            if x == 2:
                ans.append(-1)
            else:
                for i in range(1, 32):
                    if x >> i & 1 ^ 1:
                        ans.append(x ^ 1 << (i - 1))
                        break
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on iterating through each nums[i] and computing binary manipulations, roughly O(n * log(nums[i])). Space complexity is O(n) for storing the resulting ans array.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on bitwise OR patterns rather than arithmetic approaches.
question_mark
Consider how minimizing each ans[i] might conflict with satisfying the OR condition.
question_mark
Expect questions on handling edge cases when nums[i] has consecutive ones in binary.

warning

常见陷阱

外企场景

error
Assuming ans[i] can be nums[i]-1 without verifying the OR condition.
error
Ignoring binary representation patterns that affect minimal solutions.
error
Failing to handle small prime values or negative minimal results correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Construct the minimum array for bitwise AND instead of OR.
arrow_right_alt
Allow composite numbers instead of only prime numbers in nums.
arrow_right_alt
Find ans array maximizing values instead of minimizing while satisfying OR.

help

常见问题

外企场景

继续练习

#3314 构造最小位运算数组 I #3309 连接二进制表示可形成的最大数值 #3287 求出数组中最大序列值