解法一

思路和算法

数组 $\textit{nums}$ 的长度是 $n$。对于 $0 \le i < n$ 的每个下标 $i$，满足 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) = \textit{nums}[i]$。由于 $\textit{nums}[i]$ 是质数，即 $\textit{nums}[i]$ 至少等于 $2$，因此 $\textit{ans}[i]$ 一定是正整数。

最直观的计算 $\textit{ans}[i]$ 的方法是从小到大遍历每个正整数 $x$，寻找满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$ 的最小正整数 $x$ 填入 $\textit{ans}[i]$，如果不存在符合要求的正整数 $x$ 则 $\textit{ans}[i] = -1$。

根据按位或运算的性质，必有 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) \ge \textit{ans}[i]$，因此当 $\textit{ans}[i] > \textit{nums}[i]$ 时必有 $(\textit{ans}[i] ~|~ (\textit{ans}[i] + 1)) > \textit{nums}[i]$，计算 $\textit{ans}[i]$ 时只需要遍历不超过 $\textit{nums}[i]$ 的值。

代码

###Java

class Solution {
    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = find(nums.get(i));
        }
        return ans;
    }

    public int find(int num) {
        for (int i = 1; i <= num; i++) {
            if ((i | (i + 1)) == num) {
                return i;
            }
        }
        return -1;
    }
}

###C#

public class Solution {
    public int[] MinBitwiseArray(IList<int> nums) {
        int n = nums.Count;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = Find(nums[i]);
        }
        return ans;
    }

    public int Find(int num) {
        for (int i = 1; i <= num; i++) {
            if ((i | (i + 1)) == num) {
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：$O(nm)$，其中 $n$ 是数组 $\textit{nums}$ 的长度，$m$ 是数组 $\textit{nums}$ 中的最大元素。答案数组中的每个元素的计算时间都是 $O(m)$。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。

解法二

思路和算法

当存在正整数 $x$ 满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$ 时，由于 $x$ 和 $x + 1$ 当中一定有一个奇数，因此 $\textit{nums}[i]$ 一定是奇数。如果 $\textit{nums}[i]$ 是偶数，则不存在符合要求的 $x$，对应 $\textit{ans}[i] = -1$。当 $\textit{nums}[i]$ 是奇数时，可以取 $x = \textit{nums}[i] - 1$，则满足 $(x ~|~ (x + 1)) = \textit{nums}[i]$，因此如果 $\textit{nums}[i]$ 是奇数，则一定存在符合要求的 $x$。

由于 $\textit{nums}[i]$ 是质数，唯一的偶质数是 $2$，因此当 $\textit{nums}[i] = 2$ 时 $\textit{ans}[i] = -1$。当 $\textit{nums}[i] > 2$ 时 $\textit{ans}[i] > 0$，需要计算 $\textit{ans}[i]$。

考虑正整数 $x$ 和 $x + 1$ 的二进制表示的如下两种情况。

• 当 $x$ 是偶数时，$x$ 的二进制表示的最低位是 $0$，$x + 1$ 的二进制表示等于 $x$ 的二进制表示的最低位从 $0$ 变成 $1$。

• 当 $x$ 是奇数时，$x$ 的二进制表示最低位有 $k$ 个 $1$ 且从低到高第 $k$ 位等于 $0$（位数从 $0$ 开始计数），其中 $k \ge 1$，$x + 1$ 的二进制表示等于 $x$ 的二进制表示的最低 $k$ 位从 $1$ 变成 $0$ 且从低到高第 $k$ 位从 $0$ 变成 $1$。

因此，$x ~|~ (x + 1)$ 的二进制表示的结果等于 $x$ 的二进制表示的最右边的 $0$ 变成 $1$。

为了使 $\textit{ans}[i]$ 的值最小，需要找到 $\textit{nums}[i]$ 的二进制表示中的可以变成 $0$ 的最左边的 $1$，满足将 $0$ 变成 $1$ 之后在其右侧没有任何 $0$。计算方法如下。

1. 计算 $\textit{nums}[i]$ 的二进制表示的最低连续 $1$ 的最大位数 $k$，满足二进制表示最低位有 $k$ 个 $1$ 且从低到高第 $k$ 位等于 $0$（位数从 $0$ 开始计数）。

2. 计算 $\textit{ans}[i] = \textit{nums}[i] - 2^{k - 1}$。

根据位运算的性质，计算方法如下：计算 $\textit{lowbit} = ((\textit{nums}[i] + 1) ~&~ (-\textit{nums}[i] - 1)) >> 1$，则 $\textit{lowbit}$ 等于上述 $2^{k - 1}$，$\textit{ans}[i] = \textit{nums}[i] - \textit{lowbit}$。

代码

###Java

class Solution {
    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = find(nums.get(i));
        }
        return ans;
    }

    public int find(int num) {
        if (num % 2 == 0) {
            return -1;
        } else {
            int lowbit = ((num + 1) & (-num - 1)) >> 1;
            return num - lowbit;
        }
    }
}

###C#

public class Solution {
    public int[] MinBitwiseArray(IList<int> nums) {
        int n = nums.Count;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = Find(nums[i]);
        }
        return ans;
    }

    public int Find(int num) {
        if (num % 2 == 0) {
            return -1;
        } else {
            int lowbit = ((num + 1) & (-num - 1)) >> 1;
            return num - lowbit;
        }
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。答案数组中的每个元素的计算时间都是 $O(1)$。

• 空间复杂度：$O(1)$。注意返回值不计入空间复杂度。