2680. Maximum OR

MediumGreedyBit ManipulationArrayPrefix Sum
Leetcode Link

Problem Description

In this problem, you're given an array of integers nums and an integer k. Your task is to maximize the value of a bitwise OR operation over all the elements of the array, with the option to double any element of the array up to k times. Doubling an element is done by multiplying it by 2. The final result should be the maximum value obtained by performing the bitwise OR operation on all elements after at most k doublings. Bitwise OR operation takes two numbers and compares their bits, resulting in a number that has a 1 in each bit position if either of the original numbers has a 1 in that position.

Intuition

The key insight to solve this problem is understanding how the bitwise OR operation works and how doubling a number influences the result. When you apply the bitwise OR operation over an array of numbers, the resulting value has 1s in all bit positions where there is a 1 in any of the numbers. Therefore, increasing the value of one number by multiplying it by 2 essentially shifts all of the 1 bits to the left by one position. Doing this k times would shift the 1 bits to the left k times, potentially creating a larger number.

The greedy approach is based on the idea that to maximize the overall result, we should focus on doubling the numbers that contribute the most 1 bits that are not already present in the accumulated OR result. Therefore, instead of randomly distributing the doublings across different numbers, the strategy is to double the same number k times to maximally shift its 1 bits.

Preprocessing the input array to calculate suffix OR values, which represent the bitwise OR of all numbers from the current position to the end, helps to understand the impact of each element on the total OR value. Combining this with a running prefix OR value, we can assess the total OR value if we were to double the current element k times. By iterating over each array element and performing this calculation, while keeping track of the maximum OR value obtained thus far, we can arrive at the optimal solution.

Learn more about Greedy and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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.

Solution Approach

The solution approach outlined in the reference is a strategic combination of greediness, preprocessing, and bit manipulation to solve the problem.

Here are the specific steps we take in the implementation:

  1. Calculate Suffix OR: We create a suffix OR array suf that helps with understanding the impact of each element on the total OR value from that element to the end. This is achieved by iterating from the end of the nums array towards the initial element and cumulatively applying the bitwise OR operation. Therefore, suf[i] represents the OR result of nums[i] | nums[i + 1] | ... | nums[n - 1].

  2. Iterate with a Prefix OR and a Running Maximum: We keep a running prefix OR value pre that represents the cumulative OR value from the start of the array up to the current index. We also keep track of the maximum value encountered ans. At each step, we apply k doublings to the current element (nums[i]) by left-shifting its bits k times (equivalent to nums[i] << k), and then we calculate the OR with the prefix pre and suffix suf[i + 1]. The max function allows us to update ans if the newly calculated OR is greater than the previous maximum.

  3. Update Prefix OR: After handling each element, we need to update the prefix OR value pre with the current element before moving on to the next in order to properly prepare for the next iteration.

  4. Return the Maximum Value: After processing all elements, ans holds the maximum possible OR value, which we then return.

This approach is efficient because it computes the prefix and suffix OR values on the fly and only considers doubling an element at most k times. By recognizing the importance of bit positions in OR operations, it strategically selects where to apply the operation to achieve the maximum result.

In terms of algorithms and data structures:

  • The suffix OR array is a form of dynamic programming that allows for constant-time access to the OR result of all elements from any given position to the end.
  • The bit manipulation with left shifts (<<) enables efficient doubling of the elements.
  • The greedy choice is based on utilizing all k doublings on one element to maximize its contribution to the overall OR result.

The algorithm avoids unnecessary doublings by considering the impact of each bit position and prioritizing the doubling where it adds the most significant new bits to the running OR result.

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

Which of the following uses divide and conquer strategy?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we are given the following array nums and the integer k:

1nums = [3, 6, 8, 2]
2k = 3

Our goal is to maximize the bitwise OR value by doubling at most k = 3 elements.

  1. Calculate Suffix OR:

    Create the suffix OR array suf:

    • suf[3] = nums[3] = 2 (binary: 10)
    • suf[2] = nums[2] | suf[3] = 8 | 2 = 10 (binary: 1010)
    • suf[1] = nums[1] | suf[2] = 6 | 10 = 14 (binary: 1110)
    • suf[0] = nums[0] | suf[1] = 3 | 14 = 15 (binary: 1111)

    Thus, suf = [15, 14, 10, 2].

  2. Iterate with a Prefix OR and a Running Maximum:

    Initialize pre as 0 and ans as 0. Now iterate through nums:

    • For i = 0, nums[0] = 3 (binary: 11). After doubling k times: 3 << 3 = 24 (binary: 11000). The combined OR with the suffix OR is 11000 | 14 = 30 (binary: 11110). Update ans to 30.

    • Update pre to include nums[0]: pre = pre | 3 = 3 (binary: 11).

    • For i = 1, nums[1] = 6 (binary: 110). After doubling k times: 6 << 3 = 48 (binary: 110000). The combined OR with pre and suffix OR is 110000 | 11 | 10 = 50 (binary: 110010). ans remains 30 as 50 does not increase the OR value.

    • Update pre to include nums[1]: pre = 3 | 6 = 7 (binary: 111).

    • For i = 2, nums[2] = 8 (binary: 1000). After doubling k times: 8 << 3 = 64 (binary: 1000000). Combined OR with pre and suffix OR is 1000000 | 111 | 2 = 71 (binary: 1000111). Update ans to 71.

    • Update pre to include nums[2]: pre = 7 | 8 = 15 (binary: 1111).

    • For i = 3, nums[3] = 2 (binary: 10). After doubling k times: 2 << 3 = 16 (binary: 10000). Combined OR with pre is 10000 | 1111 = 31 (binary: 11111). ans remains 71 as 31 does not increase the OR value.

  3. Return the Maximum Value:

    After processing all elements, the maximum OR value we found is 71, which is in binary 1000111. Return 71 as the answer.

This walkthrough demonstrates the systematic approach of combining both bit manipulation with the greedy concept of maximizing bit shifts and using dynamic programming techniques to maintain suffix and prefix OR values.

Solution Implementation

1class Solution:
2    def maximumOr(self, nums: List[int], k: int) -> int:
3        # Length of the input list.
4        length_nums = len(nums)
5      
6        # Suffix array to store the suffix OR starting from each position.
7        suffix_or = [0] * (length_nums + 1)
8      
9        # Compute the suffix OR values in a right-to-left manner.
10        for i in range(length_nums - 1, -1, -1):
11            suffix_or[i] = suffix_or[i + 1] | nums[i]
12      
13        # Initialize answer and prefix OR.
14        max_or_result = prefix_or = 0
15      
16        # Enumerate over nums to find the maximum OR after applying the shift
17        for i, num in enumerate(nums):
18            # Calculate OR by combining current prefix OR, the shifted num, and the suffix OR;
19            # updating the max if a larger value is found.
20            max_or_result = max(max_or_result, prefix_or | (num << k) | suffix_or[i + 1])
21          
22            # Update the prefix OR accumulatively.
23            prefix_or |= num
24      
25        # Return the maximum value found.
26        return max_or_result
27
1class Solution {
2    public long maximumOr(int[] nums, int k) {
3        int length = nums.length; // Store the length of the input array
4        long[] suffixOr = new long[length + 1]; // Create an array to store suffix OR values
5        // Calculate the suffix OR values from the end of the array to the beginning
6        for (int i = length - 1; i >= 0; --i) {
7            suffixOr[i] = suffixOr[i + 1] | nums[i];
8        }
9        long maxOr = 0; // Variable to store the maximum OR result
10        long prefixOr = 0; // Variable to accumulate the prefix OR values
11      
12        // Loop through the given array
13        for (int i = 0; i < length; ++i) {
14            // Calculate the maximum OR by considering the current number shifted left by k bits,
15            // the OR of previous numbers and the OR of the remaining numbers to the right
16            maxOr = Math.max(maxOr, prefixOr | (1L * nums[i] << k) | suffixOr[i + 1]);
17            // Update the prefixOr with the current number
18            prefixOr |= nums[i];
19        }
20        // Return the maximum OR value found
21        return maxOr;
22    }
23}
24
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    long long maximumOr(std::vector<int>& nums, int k) {
8        int n = nums.size(); // Get the size of the input vector nums.
9        long long suffixOr[n + 1]; // Create an array to store the suffix OR results with an extra element for the boundary condition.
10        std::memset(suffixOr, 0, sizeof(suffixOr)); // Initialize the suffixOr array with 0.
11      
12        // Build the suffix OR array, where each element has the OR of itself and all elements to its right.
13        for (int i = n - 1; i >= 0; --i) {
14            suffixOr[i] = suffixOr[i + 1] | nums[i];
15        }
16      
17        long long maxOr = 0; // Initialize the variable to store the maximum OR value.
18        long long prefixOr = 0; // Initialize the prefix OR, which will contain the OR of all elements processed so far.
19      
20        // Iterate over all elements in the array.
21        for (int i = 0; i < n; ++i) {
22            // Calculate the maximum OR value by considering the current prefix OR, the transformed current number,
23            // and the suffix OR. The transformation shifts the current number left by 'k' bits.
24            maxOr = std::max(maxOr, prefixOr | (static_cast<long long>(nums[i]) << k) | suffixOr[i + 1]);
25            // Update the prefix OR to include the current number.
26            prefixOr |= nums[i];
27        }
28      
29        // Return the maximum calculated OR value.
30        return maxOr;
31    }
32};
33
1// Function to calculate the maximum OR value after replacing at most one integer 
2// in the array nums with any integer between 0 and 2^k - 1, inclusive.
3function maximumOr(nums: number[], k: number): number {
4    // Initialize the length of the input array.
5    const length = nums.length;
6    // Initialize the suffix array of type bigint to store cumulative OR from the end.
7    const suffixOr: bigint[] = Array(length + 1).fill(0n);
8  
9    // Populate the suffixOr array with cumulative OR values starting from the end.
10    for (let i = length - 1; i >= 0; i--) {
11        suffixOr[i] = suffixOr[i + 1] | BigInt(nums[i]);
12    }
13  
14    // Initialize the variables to store the current answer and the prefix OR.
15    let [maxOrValue, prefixOr] = [0, 0n];
16  
17    // Iterate through the nums array to find the maximum OR value.
18    for (let i = 0; i < length; i++) {
19        // Update the maxOrValue with the maximum OR value achievable by:
20        // - Taking the current prefix OR
21        // - ORing with the current number shifted left by k bits
22        // - ORing with the suffix OR of the elements to the right
23        maxOrValue = Math.max(
24            maxOrValue,
25            Number(prefixOr | (BigInt(nums[i]) << BigInt(k)) | suffixOr[i + 1])
26        );
27        // Update the prefix OR with the current number.
28        prefixOr |= BigInt(nums[i]);
29    }
30  
31    // Return the maximum OR value found.
32    return maxOrValue;
33}
34
Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Time and Space Complexity

The time complexity of the provided code is O(n). This is because there is a single loop that iterates over the array nums of size n backwards to build the suf array and another loop that goes forward through nums to compute ans. Both loops have iterations that perform a constant number of operations, therefore the time complexity remains linear in relation to the size of nums.

The space complexity of the code is O(n). Additional space is used for the suf array which is of size n + 1. Since this is proportional to the size of the original array nums, the space complexity scales linearly with the input size, hence O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching 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.

←
↑TA 👨‍🏫