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)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|