2680. Maximum OR
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 1
s 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.
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:
-
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 thenums
array towards the initial element and cumulatively applying the bitwise OR operation. Therefore,suf[i]
represents the OR result ofnums[i] | nums[i + 1] | ... | nums[n - 1]
. -
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 encounteredans
. At each step, we applyk
doublings to the current element (nums[i]
) by left-shifting its bitsk
times (equivalent tonums[i] << k
), and then we calculate the OR with the prefixpre
and suffixsuf[i + 1]
. Themax
function allows us to updateans
if the newly calculated OR is greater than the previous maximum. -
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. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
:
nums = [3, 6, 8, 2] k = 3
Our goal is to maximize the bitwise OR value by doubling at most k = 3
elements.
-
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]
. -
Iterate with a Prefix OR and a Running Maximum:
Initialize
pre
as0
andans
as0
. Now iterate throughnums
:-
For
i = 0
,nums[0] = 3 (binary: 11)
. After doublingk
times:3 << 3 = 24 (binary: 11000)
. The combined OR with the suffix OR is11000 | 14 = 30 (binary: 11110)
. Updateans
to30
. -
Update
pre
to includenums[0]
:pre = pre | 3 = 3 (binary: 11)
. -
For
i = 1
,nums[1] = 6 (binary: 110)
. After doublingk
times:6 << 3 = 48 (binary: 110000)
. The combined OR withpre
and suffix OR is110000 | 11 | 10 = 50 (binary: 110010)
.ans
remains30
as50
does not increase the OR value. -
Update
pre
to includenums[1]
:pre = 3 | 6 = 7 (binary: 111)
. -
For
i = 2
,nums[2] = 8 (binary: 1000)
. After doublingk
times:8 << 3 = 64 (binary: 1000000)
. Combined OR withpre
and suffix OR is1000000 | 111 | 2 = 71 (binary: 1000111)
. Updateans
to71
. -
Update
pre
to includenums[2]
:pre = 7 | 8 = 15 (binary: 1111)
. -
For
i = 3
,nums[3] = 2 (binary: 10)
. After doublingk
times:2 << 3 = 16 (binary: 10000)
. Combined OR withpre
is10000 | 1111 = 31 (binary: 11111)
.ans
remains71
as31
does not increase the OR value.
-
-
Return the Maximum Value:
After processing all elements, the maximum OR value we found is
71
, which is in binary1000111
. Return71
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
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.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Greedy Introduction div class responsive iframe iframe 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 div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!