3314. Construct the Minimum Bitwise Array I

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

Intuition

The solution to this problem revolves around understanding the properties of bitwise operations, specifically the OR operation. The key observation is that the result of a OR (a + 1) is always an odd number. This means that for any even nums[i], ans[i] cannot exist, as prime numbers that are even only include the number 2, which makes it impossible to satisfy the condition, thus resulting in an ans[i] of -1 when nums[i] is 2.

For an odd nums[i], we need to identify how to derive a minimal ans[i] such that ans[i] OR (ans[i] + 1) = nums[i]. To achieve this, consider the binary representation of nums[i]. We traverse from the least significant bit upwards until we find the first 0. This bit can be flipped to satisfy the condition because flipping the smallest 0 to a 1 changes the number in the least significant manner, minimizing ans[i].

The solution, therefore, involves iterating through each number in the nums array, checking if the number is 2 (setting ans[i] to -1 in this case), and otherwise finding the least significant 0 and adjusting ans[i] by flipping that specific bit to ensure minimal change in value while following the rules of the bitwise OR condition.

Solution Approach

The solution to the problem leverages bit manipulation to solve for each element in the input array nums. The steps involved in the approach are as follows:

Initialize an Output Array: Create an empty list ans to store the results for each element in the nums array.
Iterate Over nums: For each prime number x in the input array nums:
- Special Case for 2: Since 2 is the only even prime number, we cannot find a valid ans[i] such that ans[i] OR (ans[i] + 1) = 2. Therefore, append -1 to ans for this value.
- Finding ans[i] for Odd Numbers: For any odd prime number x, the task is to find the smallest integer a such that a OR (a + 1) = x.
  - Bit Manipulation: Traverse the binary representation of x starting from the least significant bit (smallest bit position). The goal is to find the first 0 bit in x.
  - Flip the Bit: For the first 0 bit found at position i, change the corresponding bit in ans[i] to 1 by using x XOR (1 << (i - 1)). This flips the bit at position i - 1 due to binary indexing starting at 0 (least significant bit).
  - Append Result: Once a is found, append it to ans.
Return the Result: After processing all elements, the function returns the array ans, which contains the minimal integers a as per the problem's conditions.

The bit manipulation ensures that we efficiently find the minimal value of ans[i] while adhering to the properties of OR operations. Here's the provided solution in Python:

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

In the solution above, the use of x >> i & 1 ^ 1 helps in identifying the first 0 bit by shifting bits to the right and checking if the result is 0. The XOR operation is then used to flip the bit at position i - 1, providing the minimum necessary change. The iteration through possible bit positions is controlled by the range 1 to 31 due to typical integer size considerations.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Consider the input nums array as [3, 2, 5, 11]. We need to find an array ans such that for each index i, ans[i] OR (ans[i] + 1) == nums[i]. Let's go through each number to illustrate the solution approach.

Analyzing nums[0] = 3:
- Binary Representation: 3 is 11 in binary.
- Identify First 0 Bit: Starting from the least significant bit, 3 is 11. The first 0 bit is at the least significant position after the two 1s.
- Bit Flipping: By flipping this bit, we find 2 because 10 in binary is just 2.
- Verification: 2 OR (2 + 1) = 2 OR 3 = 11, which equals 3.
- Result: Append 2 to ans.
Analyzing nums[1] = 2:
- Special Case: As 2 is the only even prime, it's impossible to satisfy the condition.
- Result: Append -1 to ans.
Analyzing nums[2] = 5:
- Binary Representation: 5 is 101 in binary.
- Identify First 0 Bit: The first 0 bit is at position 1 (from the right).
- Bit Flipping: Flip it to get 4 since 100 in binary equals 4.
- Verification: 4 OR (4 + 1) = 4 OR 5 = 101, which equals 5.
- Result: Append 4 to ans.
Analyzing nums[3] = 11:
- Binary Representation: 11 is 1011 in binary.
- Identify First 0 Bit: The first 0 bit appears at position 1.
- Bit Flipping: Change it to get 10 since 1010 in binary is 10.
- Verification: 10 OR (10 + 1) = 10 OR 11 = 1011, which equals 11.
- Result: Append 10 to ans.

Final result array ans is [2, -1, 4, 10].

Solution Implementation

1from typing import List
2
3class Solution:
4    def minBitwiseArray(self, nums: List[int]) -> List[int]:
5        ans = []  # Initialize an empty list to store results
6        for x in nums:
7            # If the current number is 2, append -1 to the result
8            if x == 2:
9                ans.append(-1)
10            else:
11                # Check each bit position from 1 to 31
12                for i in range(1, 32):
13                    # Check if the i-th bit is not set
14                    if (x >> i) & 1 ^ 1:
15                        # Append the number with i-th bit flipped to the result
16                        ans.append(x ^ (1 << (i - 1)))
17                        break  # Move to the next number after appending the result
18        return ans
19

1import java.util.List;
2
3class Solution {
4    public int[] minBitwiseArray(List<Integer> nums) {
5        int n = nums.size();  // Get the size of the list
6        int[] result = new int[n]; // Initialize the result array
7
8        // Iterate through each number in the list
9        for (int i = 0; i < n; ++i) {
10            int currentNumber = nums.get(i); // Get the current number
11          
12            // If the number is 2, set the result at this index to -1
13            if (currentNumber == 2) {
14                result[i] = -1;
15            } else {
16                // Check each bit position
17                for (int j = 1; j < 32; ++j) {
18                    // Check if the j-th bit is 0
19                    if ((currentNumber >> j & 1) == 0) {
20                        // Flip the (j-1)-th bit of the current number and store in result
21                        result[i] = currentNumber ^ (1 << (j - 1));
22                        break; // Exit loop once modified
23                    }
24                }
25            }
26        }
27        return result; // Return the result array
28    }
29}
30

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<int> minBitwiseArray(vector<int>& nums) {
7        vector<int> ans; // Result vector to store the processed numbers
8        for (int num : nums) { // Loop through each element in nums
9            if (num == 2) {
10                ans.push_back(-1); // Special case: if num is 2, push -1 to the result
11            } else {
12                for (int i = 1; i < 32; ++i) { // Check each bit from position 1 to 31
13                    // Check if the i-th bit of num is 0 
14                    if (!(num >> i & 1)) {
15                        // Flip the (i-1)-th bit of num and push the result
16                        ans.push_back(num ^ (1 << (i - 1))); 
17                        break; // Exit the loop after finding the first 0 bit
18                    }
19                }
20            }
21        }
22        return ans; // Return the modified vector
23    }
24};
25

1function minBitwiseArray(nums: number[]): number[] {
2    const result: number[] = []; // Array to store the final results
3
4    for (const num of nums) {
5        if (num === 2) {
6            // If the number is 2, directly append -1 to the result
7            result.push(-1);
8        } else {
9            // Try to find the smallest number by flipping one bit
10            for (let i = 1; i < 32; ++i) {
11                // Check each bit starting from the least significant
12                if (((num >> i) & 1) ^ 1) {
13                    // Find the first '0' bit and flip it
14                    result.push(num ^ (1 << (i - 1)));
15                    break;
16                }
17            }
18        }
19    }
20
21    return result; // Return the computed array
22}
23

Time and Space Complexity

The time complexity of the code is O(n × 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 element in the nums list, up to log M bit positions are checked in the worst case scenario.

The space complexity is O(1), ignoring the space consumption of the ans array. This is because the algorithm only uses a constant amount of extra space aside from the input and output storage.

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

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

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know