Skip to content

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 for ans[0] that satisfies ans[0] OR (ans[0] + 1) = 2, so ans[0] = -1.
  • For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 3 is 1, because 1 OR (1 + 1) = 3.
  • For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 5 is 4, because 4 OR (4 + 1) = 5.
  • For i = 3, the smallest ans[3] that satisfies ans[3] OR (ans[3] + 1) = 7 is 3, because 3 OR (3 + 1) = 7.

Example 2:

Input: nums = [11,13,31]

Output: [9,12,15]

Explanation:

  • For i = 0, the smallest ans[0] that satisfies ans[0] OR (ans[0] + 1) = 11 is 9, because 9 OR (9 + 1) = 11.
  • For i = 1, the smallest ans[1] that satisfies ans[1] OR (ans[1] + 1) = 13 is 12, because 12 OR (12 + 1) = 13.
  • For i = 2, the smallest ans[2] that satisfies ans[2] OR (ans[2] + 1) = 31 is 15, because 15 OR (15 + 1) = 31.

 

Constraints:

  • 1 <= nums.length <= 100
  • 2 <= nums[i] <= 1000
  • nums[i] is a prime number.

Solutions

Solution 1: Bit Manipulation

Thinking

\(a \lor (a+1)\) always turns on the lowest zero of \(a\), so the result is odd. The only even prime here is \(2\), which has no solution.

For an odd \(x\), the smallest \(a\) is obtained by turning off the one just below \(x\)'s lowest zero, which still satisfies \(a \lor (a+1)=x\).

Scan bits from low to high, take the first zero at position \(i\), and set \(a = x \oplus 2^{i-1}\). The constraints make a 32-bit scan cheap.

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
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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn min_bitwise_array(nums: Vec<i32>) -> Vec<i32> {
        let mut ans = Vec::with_capacity(nums.len());
        for x in nums {
            if x == 2 {
                ans.push(-1);
            } else {
                for i in 1..32 {
                    if (((x >> i) & 1) ^ 1) == 1 {
                        ans.push(x ^ (1 << (i - 1)));
                        break;
                    }
                }
            }
        }
        ans
    }
}

Comments