题目描述

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

• ans[i] OR (ans[i] + 1) == nums[i]
• 除此以外，你需要 最小化 结果数组里每一个 ans[i]。

如果没法找到符合 条件 的 ans[i]，那么 ans[i] = -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。

输入：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^9
• nums[i] 是一个质数。

算法1

(思维题) $O(n \log U)$

1. 观察题目条件的性质，注意到偶数是不存在答案的。
2. 对于奇数，从二进制最低位寻找第一次出现的位置 $p$，满足第 $p$ 位为 $1$，且第 $p+1$ 位为 $0$，然后将第 $p$ 位变为 $0$ 就是答案。例如数字 $xxxx01111$ 的答案就是 $xxxx00111$。

时间复杂度

• 每个数字都需要 $O(\log U)$ 的时间寻找答案，故时间复杂度为 $O(n \log U)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        for (int &x : nums) {
            if (x == 2) {
                x = -1;

                continue;
            }

            for (int j = 1; j < 31; j++)
                if (!((x >> j) & 1)) {
                    x ^= (1 << (j - 1));

                    break;
                }
        }

        return nums;
    }
};

算法2

(思维题，位运算) $O(n)$

1. 沿用算法 1，寻找 $p$ 的过程可以不通过遍历二进制位。
2. 将 $nums(i)$ 取反，记为 $x$，然后通过 $x$ 与 $-x$ 进行 AND 操作得到 $x$ 的 lowbit，将这个 lowbit 右移一位就得到了 $p$ 的位置。再与原数字取

时间复杂度

• 每个数字仅需要常数的时间寻找答案，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        for (int &x : nums) {
            if (x == 2) {
                x = -1;
            } else {
                int t = ~x;
                x ^= ((t & -t) >> 1);
            }
        }

        return nums;
    }
};