Welcome to Subscribe On Youtube
3314. Construct the Minimum Bitwise Array I
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) = 3
is1
, because1 OR (1 + 1) = 3
. - For
i = 2
, the smallestans[2]
that satisfiesans[2] OR (ans[2] + 1) = 5
is4
, because4 OR (4 + 1) = 5
. - For
i = 3
, the smallestans[3]
that satisfiesans[3] OR (ans[3] + 1) = 7
is3
, 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) = 11
is9
, because9 OR (9 + 1) = 11
. - For
i = 1
, the smallestans[1]
that satisfiesans[1] OR (ans[1] + 1) = 13
is12
, because12 OR (12 + 1) = 13
. - For
i = 2
, the smallestans[2]
that satisfiesans[2] OR (ans[2] + 1) = 31
is15
, because15 OR (15 + 1) = 31
.
Constraints:
1 <= nums.length <= 100
2 <= nums[i] <= 1000
nums[i]
is a prime number.
Solutions
Solution 1: Bit Manipulation
For an integer $a$, the result of $a \lor (a + 1)$ is always odd. Therefore, if $\text{nums[i]}$ is even, then $\text{ans}[i]$ does not exist, and we directly return $-1$. In this problem, $\textit{nums}[i]$ is a prime number, so to check if it is even, we only need to check if it equals $2$.
If $\text{nums[i]}$ is odd, suppose $\text{nums[i]} = \text{0b1101101}$. Since $a \lor (a + 1) = \text{nums[i]}$, this is equivalent to changing the last $0$ bit of $a$ to $1$. To solve for $a$, we need to change the bit after the last $0$ in $\text{nums[i]}$ to $0$. We start traversing from the least significant bit (index $1$) and find the first $0$ bit. If it is at position $i$, we change the $(i - 1)$-th bit of $\text{nums[i]}$ to $1$, i.e., $\text{ans}[i] = \text{nums[i]} \oplus 2^{i - 1}$.
By traversing all elements in $\text{nums}$, we can obtain the answer.
The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the length of the array $\text{nums}$ and the maximum value in the array, respectively. Ignoring the space consumption of the answer array, the space complexity is $O(1)$.
-
class Solution { public int[] minBitwiseArray(List<Integer> nums) { int n = nums.size(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int x = nums.get(i); if (x == 2) { ans[i] = -1; } else { for (int j = 1; j < 32; ++j) { if ((x >> j & 1) == 0) { ans[i] = x ^ 1 << (j - 1); break; } } } } return ans; } }
-
class Solution { public: vector<int> minBitwiseArray(vector<int>& nums) { vector<int> ans; for (int x : nums) { if (x == 2) { ans.push_back(-1); } else { for (int i = 1; i < 32; ++i) { if (x >> i & 1 ^ 1) { ans.push_back(x ^ 1 << (i - 1)); break; } } } } return ans; } };
-
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
-
func minBitwiseArray(nums []int) (ans []int) { for _, x := range nums { if x == 2 { ans = append(ans, -1) } else { for i := 1; i < 32; i++ { if x>>i&1 == 0 { ans = append(ans, x^1<<(i-1)) break } } } } return }
-
function minBitwiseArray(nums: number[]): number[] { const ans: number[] = []; for (const x of nums) { if (x === 2) { ans.push(-1); } else { for (let i = 1; i < 32; ++i) { if (((x >> i) & 1) ^ 1) { ans.push(x ^ (1 << (i - 1))); break; } } } } return ans; }