3315. Construct the Minimum Bitwise Array II

MediumBit ManipulationArray

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The solution involves a key observation about the operation a OR (a + 1). For any integer a, this result is always odd. Thus, if nums[i] is even, it is impossible to find such an a, and we must return -1. Since nums consists of prime numbers, the only even possibility is 2.

For odd nums[i], the goal is to construct ans[i] such that ans[i] OR (ans[i] + 1) equals nums[i]. This can be done by taking advantage of binary properties. Specifically, we need to identify a 0 bit in nums[i] and flip it to become 1 to find a.

By finding the position of the first 0 bit from the least significant bit, flipping the previous bit, and using the resultant value, we determine ans[i]. This approach minimizes ans[i] while satisfying the necessary condition.

Solution Approach

The solution uses bit manipulation to achieve the desired transformation while meeting the problem's constraints. Here's a step-by-step walk-through of the implementation:

Initialize an Array:
- Create an empty list ans to store the result.
Iterate Through Each Element in nums:
- For each element x in nums:
  - Check whether x equals 2. Since 2 is the only even prime number, if x is 2, append -1 to ans because it's impossible to find such an integer a.
  - If x is not 2, proceed with bit manipulation.
Bit Manipulation for Odd Numbers:
- Iterate the possible positions from 1 to 31 (assuming 32-bit integers).
  - For each position i, check if the (i-1)-th bit of x is 0 (using (x >> i) & 1 ^ 1).
  - If it is, calculate a by toggling the (i-1)-th bit in x. This can be done using x ^ (1 << (i - 1)).
  - Append this value to ans.
  - Break out of the inner loop since you have found the necessary ans[i].
Return the Result:
- After processing all numbers in nums, return ans.

This approach efficiently uses the properties of binary numbers and bit manipulation to derive the minimal ans[i] value for each prime number in nums.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a sample array nums = [3, 5, 13, 2] to demonstrate the solution approach.

Initialize the Array:
- Start by creating an empty list ans = [].
Iterate Through Each Element in nums:
- First iteration: Consider x = 3.
  - 3 is odd, so proceed with bit manipulation.
  - Check the bit positions:
    1. (3 >> 1) & 1 is 1, so continue.
    2. (3 >> 2) & 1 is 0, identify a = 3 ^ (1 << 1) = 3 ^ 2 = 1.
  - Append 1 to ans, resulting in ans = [1].
- Second iteration: Consider x = 5.
  - 5 is odd, so proceed with bit manipulation.
  - Check the bit positions:
    1. (5 >> 1) & 1 is 0, identify a = 5 ^ (1 << 1) = 5 ^ 2 = 7.
  - Append 4 to ans, resulting in ans = [1, 4].
- Third iteration: Consider x = 13.
  - 13 is odd, so proceed with bit manipulation.
  - Check the bit positions:
    1. (13 >> 1) & 1 is 0, identify a = 13 ^ (1 << 1) = 13 ^ 2 = 15.
  - Append 12 to ans, resulting in ans = [1, 4, 12].
- Fourth iteration: Consider x = 2.
  - Since 2 is the only even prime number, append -1 to ans.
  - Now, ans = [1, 4, 12, -1].
Return the Result:
- The final ans array is [1, 4, 12, -1].

This walkthrough shows how each ans[i] is determined using bit manipulation, resulting in the desired outcome.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minBitwiseArray(self, nums: List[int]) -> List[int]:
5        ans = []
6        # Iterate over each number in the input list
7        for x in nums:
8            # Special case: if the number is 2, append -1 to the result list
9            if x == 2:
10                ans.append(-1)
11            else:
12                # Iterate over bit positions from 1 to 31
13                for i in range(1, 32):
14                    # Check if the i-th bit of x is 0 using bitwise operations
15                    if (x >> i) & 1 == 0:
16                        # Toggle the (i-1)-th bit of x and append to the result
17                        ans.append(x ^ (1 << (i - 1)))
18                        break  # Exit the loop after finding the first unset bit
19        return ans
20

1import java.util.List;
2
3class Solution {
4    // This method calculates a new array by performing bitwise operations on the input list.
5    public int[] minBitwiseArray(List<Integer> nums) {
6        // Get the size of the input list.
7        int n = nums.size();
8      
9        // Initialize an array to store the result.
10        int[] result = new int[n];
11      
12        // Iterate through each element in the list.
13        for (int i = 0; i < n; ++i) {
14            int current = nums.get(i);
15          
16            // Directly set the result to -1 if the element is 2.
17            if (current == 2) {
18                result[i] = -1;
19            } else {
20                // Find the first position where the bit is 0 and set the result as the number XOR with 1 shifted left by (j - 1).
21                for (int j = 1; j < 32; ++j) {
22                    // Check if the j-th bit is 0.
23                    if ((current >> j & 1) == 0) {
24                        // Set the result to the number XORed with a number having a 1 at (j-1) position.
25                        result[i] = current ^ (1 << (j - 1));
26                        break;  // Exit the loop after updating the result.
27                    }
28                }
29            }
30        }
31        return result;  // Return the resulting array.
32    }
33}
34

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<int> minBitwiseArray(vector<int>& nums) {
7        vector<int> result; // This will hold the final result
8        for (int x : nums) { // Iterate through each element in the input vector
9            if (x == 2) {
10                result.push_back(-1); // If the element is 2, append -1 to the result
11            } else {
12                // Find the rightmost '0' bit in the binary representation of the number
13                // and toggle it to '1'
14                for (int i = 1; i < 32; ++i) { // Check up to the 31st bit (0-indexed)
15                    if (((x >> i) & 1) == 0) { // Check if the i-th bit is '0'
16                        result.push_back(x ^ (1 << (i - 1))); // Toggle the (i-1)-th bit and add to result
17                        break; // Exit the loop after toggling the first '0' found
18                    }
19                }
20            }
21        }
22        return result; // Return the modified vector
23    }
24};
25

1function minBitwiseArray(nums: number[]): number[] {
2    // Initialize an array to store the resultant numbers
3    const ans: number[] = [];
4  
5    // Iterate over each number in the input array
6    for (const x of nums) {
7        // Check if the number is equal to 2
8        if (x === 2) {
9            // If so, append -1 to the result array
10            ans.push(-1);
11        } else {
12            // Otherwise, iterate over the bits from 1 to 31
13            for (let i = 1; i < 32; ++i) {
14                // Check if the i-th bit of the number is 0
15                if (((x >> i) & 1) ^ 1) {
16                    // If so, flip the previous bit from 0 to 1 and append to the result array
17                    ans.push(x ^ (1 << (i - 1)));
18                    // Break the loop as we only need to flip one bit
19                    break;
20                }
21            }
22        }
23    }
24    return ans;
25}
26

Time and Space Complexity

The time complexity of the code is O(n \times \log M), where n is the length of the array nums, and M is the maximum value in the array. This complexity arises because for each number in nums, the code performs a loop that runs at most 31 iterations (since x is a 32-bit integer), effectively checking bit positions to find the necessary transformation, which can be approximated as O(\log M).

The space complexity is O(1), ignoring the space for the result array. This is because the code uses a fixed amount of additional space that does not depend on the input size. The extra space is mainly used for the loop counter and the temporary variables, which are constants.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know