3022. Minimize OR of Remaining Elements Using Operations

HardGreedyBit ManipulationArray
Leetcode Link

Problem Description

You are provided with an array of integers called nums and another integer k. Your objective is to minimize the value of the bitwise OR (|) of the array's elements. You are allowed to perform up to k operations. In a single operation, you can pick any element nums[i], except the last one, and replace both nums[i] and nums[i + 1] with nums[i] & nums[i + 1], where & represents the bitwise AND operation. The problem asks for the smallest possible bitwise OR value of the array after performing no more than k operations.

Intuition

To solve this problem, we need to understand how bitwise operations work. Bitwise AND (&) reduces the set bits so, for any two numbers, x & y will have fewer or equal set bits compared to x | y. So performing the AND operation will not increase the bitwise AND result but may reduce it.

The approach to finding the minimum bitwise OR hinges on handling the individual bits of the integers. The solution iterates over the bits from the most significant bit to the least significant bit (from left to right). For each bit position, it checks whether setting that bit could reduce the overall OR of the array without exceeding k operations.

The solution maintains two variables, ans and rans. ans is the current running result for the minimum possible value of bitwise OR, and rans is for the result if we decide not to set the current bit under examination.

The cnt variable keeps track of how many numbers still have the current bit set after applying the AND operation with ans + (1 << i) (which is considering setting the current bit). If cnt is greater than k, it means we cannot set this bit in the result since we do not have enough operations left to eliminate the set bits in all elements by doing AND operations. Therefore, rans must include this bit.

On completion, rans will have the minimum bitwise OR value without exceeding k operations, as it correctly takes into account whether or not we can afford to set each bit considering the remaining allowable operations.

Learn more about Greedy patterns.

Solution Approach

In the provided implementation, the idea is to find the minimum possible value of the bitwise OR of the array after up to k operations. The solution uses bit manipulation and greedy strategy to achieve this.

The algorithm proceeds as follows:

  1. Initialize two variables, ans and rans, to 0. ans serves as a partial answer considering the addition of the current bit, and rans is the result if we decide not to allow the current bit to be set.

  2. Iterate over the bit positions from the 29th bit (considering 32-bit integers) to the 0th bit:

    • Calculate test by setting the current ith bit, on top of the partial answer ans.

    • Initialize cnt to count how many numbers, after the AND operation with test, still keep the current bit. Initialize val to 0, representing the resulting AND of the numbers while considering the bit of interest.

    • Iterate over each number in nums and apply the AND operation with test to update val. The val variable accumulates the result of bitwise AND on the current bit position.

      • If val is non-zero after the AND operation, increment cnt.
    • If the count cnt is greater than k, it implies we can't afford to set this bit with the remaining number of operations. In that case, set the current bit in rans.

    • If cnt is less than or equal to k, we can set this bit in ans and continue potentially setting more bits in subsequent iterations.

  3. By the end of the loop, rans will hold the minimum possible value of the bitwise OR after at most k operations.

The use of ans and rans along with the count cnt allows us to determine, for each bit, whether setting it would leave us with a value that exceeds the allowed number of operations. By greedily attempting to set each bit starting from the most significant and moving to the least significant, we ensure that we are minimizing the OR value as much as possible.

This algorithm relies on bit manipulation by individually examining each bit position across all numbers in the array. By operating on each bit, we are breaking down the problem into smaller parts, which makes it more tractable since bitwise AND and OR operations are straightforward for individual bits. The greedy aspect comes into play by deciding whether to set a bit in our answer based on current information and what is allowed by our constraint k.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the following input:

  • nums = [14, 7, 3]
  • k = 1

The binary representations of the numbers in the array are:

  • 14 in binary: 1110
  • 7 in binary: 0111
  • 3 in binary: 0011

Now, let's apply the algorithm step by step:

  1. We initialize ans = 0 and rans = 0. These will keep track of the bitwise OR value as we proceed.

  2. We iterate over the bit positions from the 29th to the 0th bit. Since the example integers are small, we'll start from the 3rd bit because the higher bits are 0 for all numbers.

  3. For the 3rd bit (i = 3), we calculate test = ans | (1 << 3) which is 1000 in binary (8 in decimal).

  4. We then initialize cnt = 0 and val = 0 and iterate over each number in nums, &-ing each number with test to determine which numbers would retain the 3rd bit when AND-ed with test. Since none of the numbers in nums has a higher bit than 3, cnt remains 0, and thus we proceed without increasing rans, but we set bit 3 in ans making ans = 1000.

  5. For the 2nd bit (i = 2), we would calculate test = ans | (1 << 2) which gives us 1100 in binary. We iterate over the numbers again and find that only 14 (1110) would retain the 2nd bit when AND-ed with test. So cnt = 1 which is <= k. Therefore, we do not set the 2nd bit in rans and ans becomes 1100.

  6. For the 1st bit (i = 1), we calculate test = ans | (1 << 1) which is 1110 in binary. Similarly, cnt would be 1 since only 14 has the 1st bit set when AND-ed with 1110. Again, cnt is <= k, we don't set the 1st bit in rans, and now ans is 1110.

  7. Lastly, we perform the same check for the 0th bit (i = 0), test becomes 1111. Now, all numbers 14, 7, 3 have the 0th bit set when AND-ed with test, giving us a cnt of 3, which is greater than our k = 1. So we cannot unset this bit with our k operations. We add the 0th bit to rans by setting it, making rans = 0001.

By the end of the process, we've got an ans of 1110 (14 in decimal) and a rans of 0001 (1 in decimal), which means our minimum possible bitwise OR value after a maximum of 1 operation is 1. This is because we can perform a single AND operation on the last two elements (7 & 3) to get 7 & 3 which is 0111 & 0011 equals 0011 (3 in decimal). Then, performing the OR operation across the array 14 | 3 gives us 1110 | 0011 which equals 1111. However, since we've determined through the algorithm that we can set the 0th bit in rans, rans = 0001 is the smallest we can achieve. Now, if we replace 14 and 7 with their AND, we have nums = [14 & 7, 3] which equals [4, 3]. The | of 4 and 3 is 4 | 3 which is 0100 | 0011 equals 0111 (7 in decimal). However, since we only made one operation to replace two elements with their AND, and rans = 0001 signifies that our algorithm indicates the minimum OR can be 0001 (1 in decimal), we have achieved a minimum bitwise OR of 1.

Thus, by following the steps, we have determined that we could minimize the bitwise OR to 1 after at most one operation. This walk-through demonstrates how the given algorithm leverages bit manipulation and a greedy approach to reduce the bitwise OR of an array in a limited number of operations.

Solution Implementation

1class Solution:
2    def minOrAfterOperations(self, nums: List[int], k: int) -> int:
3        # Initialize the running minimum OR value and the result
4        min_or_value = 0
5        result = 0
6        # Iterate over the bit positions from 29 down to 0
7        for bit_position in range(29, -1, -1):
8            # Calculate a test OR value by setting the current bit
9            test_or = min_or_value | (1 << bit_position)
10            # Initialize counters for the number of numbers meeting the criteria
11            count_met = 0
12            current_val = 0
13            # Check each number against the test OR value
14            for num in nums:
15                # Calculate the AND of the current number and the test OR value
16                if current_val == 0:
17                    current_val = test_or & num
18                else:
19                    current_val &= test_or & num
20                # If the result is non-zero, the criterion is met
21                if current_val:
22                    count_met += 1
23            # If the count is greater than k, do not include this bit in the final result
24            if count_met > k:
25                result |= (1 << bit_position)
26            # Otherwise, include this bit in the running minimum OR value
27            else:
28                min_or_value |= (1 << bit_position)
29        # Return the calculated result
30        return result
31
1class Solution {
2    public int minOrAfterOperations(int[] nums, int k) {
3        // Initialize the answer and the running answer variables
4        int answer = 0;
5        int runningAnswer = 0;
6
7        // Start from the 29th bit (assuming 32-bit integers) and work down to the 0th bit
8        for (int i = 29; i >= 0; i--) {
9            // Calculate a test value by setting the i-th bit of the current answer
10            int test = answer + (1 << i);
11          
12            // Initialize the counter for the number of nums values that have the i-th bit set
13            int count = 0;
14            // Initialize the value to store the result of the AND operation
15            int andResult = 0;
16          
17            // Iterate through all numbers in the input array
18            for (int num : nums) {
19                // When andResult is zero, perform AND operation between test and the current number
20                if (andResult == 0) {
21                    andResult = test & num;
22                } else {
23                    // If andResult is not zero, accumulate the AND result with the current AND operation
24                    andResult &= test & num;
25                }
26              
27                // Increment the count if the result of the AND operation is not zero
28                if (andResult != 0) {
29                    count++;
30                }
31            }
32          
33            // If count exceeds k, only update the running answer with the i-th bit set
34            if (count > k) {
35                runningAnswer += (1 << i);
36            } else {
37                // Otherwise, update the answer with the i-th bit set
38                answer += (1 << i);
39            }
40        }
41      
42        // Return the running answer value which is the correct minimum OR value after k operations
43        return runningAnswer;
44    }
45}
46
1class Solution {
2public:
3    // Function to find the minimum OR value after performing operations.
4    int minOrAfterOperations(vector<int>& nums, int k) {
5        int possibleAnswer = 0; // Variable to store the possible OR result
6        int result = 0; // Variable to store the final OR result
7      
8        // Iterate through each bit position starting from the highest (29th bit) to the lowest
9        for (int i = 29; i >= 0; --i) {
10            int testValue = possibleAnswer + (1 << i); // Create a test value by setting the i-th bit
11            int count = 0; // Counter to store how many numbers have a non-zero bit at the i-th position
12            int runningAnd = 0; // Variable to store the running AND of nums bitwise AND with testValue
13          
14            // Iterate through all elements in the nums array
15            for (auto number : nums) {
16                if (runningAnd == 0) {
17                    // `&=`, when runningAnd is 0, will always result in 0. Thus, it's equivalent to `runningAnd = testValue & number;`
18                    runningAnd = testValue & number;
19                } else {
20                    // Perform the AND operation with testValue and the current number, then AND with runningAnd
21                    runningAnd &= testValue & number;
22                }
23                if (runningAnd) {
24                    // Increase the counter if runningAnd has a non-zero bit at the i-th position
25                    count++;
26                }
27            }
28          
29            // If the count is greater than k, add the bit to the result
30            if (count > k) {
31                result += (1 << i);
32            } else {
33                // If not, add the bit to the possibleAnswer to maintain state for the next iteration
34                possibleAnswer += (1 << i);
35            }
36        }
37
38        return result; // Return the final result
39    }
40};
41
1/** Function to find the minimum OR value after performing operations. */
2function minOrAfterOperations(nums: number[], k: number): number {
3    let possibleAnswer: number = 0; // Variable to store the possible OR result
4    let result: number = 0; // Variable to store the final OR result
5
6    // Iterate through each bit position starting from the highest (29th bit) to the lowest
7    for (let i: number = 29; i >= 0; --i) {
8        let testValue: number = possibleAnswer + (1 << i); // Create a test value by setting the i-th bit
9        let count: number = 0; // Counter to store how many numbers have a non-zero bit at the i-th position
10        let runningAnd: number = 0; // Variable to store the running AND of nums bitwise AND with the test value
11      
12        // Iterate through all elements in the nums array
13        for (let number of nums) {
14            if (runningAnd === 0) {
15                // `&=`, when runningAnd is 0, will always result in 0. Thus, it's equivalent to `runningAnd = testValue & number;`
16                runningAnd = testValue & number;
17            } else {
18                // Perform the AND operation with testValue and the current number, then AND with runningAnd
19                runningAnd &= testValue & number;
20            }
21            if (runningAnd) {
22                // Increase the counter if runningAnd has a non-zero bit at the i-th position
23                count++;
24            }
25        }
26      
27        // If the count is greater than k, add the bit to the result
28        if (count > k) {
29            result += (1 << i);
30        } else {
31            // If not, retain the bit in possibleAnswer to maintain state for the next iteration
32            possibleAnswer += (1 << i);
33        }
34    }
35
36    return result; // Return the final result
37}
38

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed as follows:

  • There is an outer loop that iterates from 29 down to 0. This loop runs exactly 30 times, which corresponds to the 30 bits in the integer representation (assuming a 32-bit integer where the last two bits are used for sign representation in most cases).

  • Inside the outer loop, there is an inner loop that iterates through all the num elements in the nums list. If n is the size of the nums list, then this loop runs n times for each iteration of the outer loop.

  • Within the inner loop, basic bit manipulation operations are performed (such as AND operations and checks). These operations are constant time.

Considering the above, we can determine that the time complexity is O(30 * n) which simplifies to O(n) because the 30 is a constant factor and does not depend on the size of the input.

Space Complexity

Analyzing the space complexity:

  • We have integer variables ans, rans, test, cnt, and val which all use constant space.

  • There is no additional data structure that scales with the input size.

Therefore, the space complexity is O(1) because the memory usage does not increase with the size of the input list nums.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄