Description
You are given an array nums consisting of n prime integers.
You need to construct an array ans of length n, such that, for each index i, the bitwise OR of ans[i] and ans[i] + 1 is equal to nums[i], i.e. ans[i] OR (ans[i] + 1) == nums[i].
Additionally, you must minimize each value of ans[i] in the resulting array.
If it is not possible to find such a value for ans[i] that satisfies the condition, then set ans[i] = -1.
Example 1:
Input: nums = [2,3,5,7]
Output: [-1,1,4,3]
Explanation:
- For
i = 0, as there is no value forans[0]that satisfiesans[0] OR (ans[0] + 1) = 2, soans[0] = -1. - For
i = 1, the smallestans[1]that satisfiesans[1] OR (ans[1] + 1) = 3is1, because1 OR (1 + 1) = 3. - For
i = 2, the smallestans[2]that satisfiesans[2] OR (ans[2] + 1) = 5is4, because4 OR (4 + 1) = 5. - For
i = 3, the smallestans[3]that satisfiesans[3] OR (ans[3] + 1) = 7is3, because3 OR (3 + 1) = 7.
Example 2:
Input: nums = [11,13,31]
Output: [9,12,15]
Explanation:
- For
i = 0, the smallestans[0]that satisfiesans[0] OR (ans[0] + 1) = 11is9, because9 OR (9 + 1) = 11. - For
i = 1, the smallestans[1]that satisfiesans[1] OR (ans[1] + 1) = 13is12, because12 OR (12 + 1) = 13. - For
i = 2, the smallestans[2]that satisfiesans[2] OR (ans[2] + 1) = 31is15, because15 OR (15 + 1) = 31.
Constraints:
1 <= nums.length <= 1002 <= nums[i] <= 109nums[i]is a prime number.
Solutions
This function finds the minimum value for each number in the input array such that when bitwise-OR'd with that value plus one, it equals the original number. For each number, it first checks if it's even — if so, it returns -1 since no valid value exists. For odd numbers, it converts the number to binary and iterates through each bit position containing a 1. For each position, it tries subtracting the corresponding power of 2 as a candidate, then tests if candidate | (candidate + 1) equals the original number. When a valid candidate is found, it's the minimum value because the algorithm tests positions from the most significant bit downward, and the bitwise operation x | (x+1) fills the gap between consecutive bits.
/**
* @param {number[]} nums
* @return {number[]}
*/
var minBitwiseArray = function(nums) {
let res = [];
for (const num of nums) {
let cur = -1;
if (num % 2 === 0) {
res.push(cur);
continue;
}
const bin = num.toString(2);
for (let i = 0; i < bin.length; i++) {
if (bin[i] === '1') {
const candidate = num - 2 ** (bin.length - 1 - i);
if ((candidate | (candidate + 1)) === num) {
cur = candidate;
break;
}
}
}
res.push(cur);
}
return res;
};
// 3 - 011 -> 001
// 5 - 101 -> 100
// 7 - 111 -> 011
// 11 - 1011 -> 1001