Leetcode 2680: Maximum OR
You are given a 0-indexed integer array
nums of length n and an integer k. In each operation, you can pick an element from the array and multiply it by 2. Your goal is to determine the maximum possible value of the bitwise OR of all elements in the array after applying the operation at most k times.Problem
Approach
Steps
Complexity
Input: You are given a list of integers `nums` and an integer `k` which represents the maximum number of operations allowed.
Example: Input: nums = [5, 3, 7], k = 1
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 15
Output: Return the maximum possible value of the bitwise OR after applying the operation at most `k` times.
Example: Output: 15
Constraints:
• The result should be a non-negative integer.
Goal: The goal is to maximize the bitwise OR of the array after modifying elements using the operation as optimally as possible.
Steps:
• Step 1: Iterate over each element of the array.
• Step 2: For each element, calculate the result of multiplying it by 2 for up to `k` times and calculate the resulting bitwise OR.
• Step 3: Track the maximum bitwise OR across all possible operations.
Goal: Ensure that the solution works efficiently for large inputs and handles all specified constraints.
Steps:
• Ensure the solution runs efficiently for arrays with up to 10^5 elements.
Assumptions:
• All input values are within the specified constraints.
• The solution should efficiently handle the maximum possible size of the array.
• Input: Input: nums = [5, 3, 7], k = 1
• Explanation: In the first operation, if we multiply 3 by 2, the new array becomes [5, 6, 7]. The bitwise OR of 5, 6, and 7 is 7. Thus, the final result is 7.
• Input: Input: nums = [8, 1, 2], k = 2
• Explanation: If we multiply 8 by 2 twice, we get [32, 1, 2]. The bitwise OR of 32, 1, and 2 is 35. Thus, the final result is 35.
Approach: The solution involves using a greedy approach to maximize the OR by considering the impact of multiplying elements by 2 up to `k` times and calculating the OR for each possible modification.
Observations:
• We want to maximize the OR, which means we need to focus on the higher values in the array and determine if multiplying them will result in a higher OR.
• It might be useful to calculate the OR for each possible operation and compare the results.
Steps:
• Step 1: Calculate the prefix and suffix ORs for the array to optimize the process of combining ORs when modifying individual elements.
• Step 2: For each element, multiply it by powers of 2 up to `k` times and compute the resulting OR with its neighbors.
• Step 3: Keep track of the highest OR encountered and return it as the final result.
Empty Inputs:
• The array will always contain at least one element, so there are no empty arrays.
Large Inputs:
• The solution must be optimized to handle arrays with up to 10^5 elements efficiently.
Special Values:
• If all elements are the same, multiplying any of them will still yield the same OR, and the OR should be calculated based on that.
Constraints:
• Ensure that the solution is efficient for large values of `nums[i]` and handles arrays up to the size limit.
long long maximumOr(vector<int>& nums, int k)
{
//prefix or
//suffix or
vector<long long>prefixor;
for(int i = 0 ; i < nums.size() ; i++)
{
if(i == 0) prefixor.push_back((1LL * nums[i]));
else prefixor.push_back(((1LL*prefixor.back()) | (1LL*nums[i])));
}
vector<long long>suffixor;
for(int i = nums.size() - 1; i >= 0; i--)
{
if(i == (nums.size()-1)) suffixor.push_back((1LL * nums[i]));
else suffixor.push_back(((1LL*suffixor.back()) | (1LL*nums[i])));
}
reverse(suffixor.begin(),suffixor.end());
long long ans = 0;
for(int i = 0 ; i < nums.size() ; i++)
{
long long int left = 0;
long long int self;
long long int right = 0;
if((i-1) >= 0)
{
left = prefixor[i-1];
}
self = (nums[i] * pow(2,k));
if((i+1) <= nums.size()-1)
{
right = suffixor[i+1];
}
ans = max(ans , left | self | right);
}
return ans;
}
1 : Function Definition
long long maximumOr(vector<int>& nums, int k)
The function 'maximumOr' is defined to take a vector of integers 'nums' and an integer 'k'. It calculates the maximum value of the bitwise OR operation across modified elements of the array.
2 : Prefix OR Vector Initialization
vector<long long>prefixor;
A vector 'prefixor' is initialized to store the cumulative OR values from the start of the array.
3 : Prefix OR Calculation Loop
for(int i = 0 ; i < nums.size() ; i++)
A loop iterates through the 'nums' array to calculate the prefix OR values.
4 : First Prefix OR Value
if(i == 0) prefixor.push_back((1LL * nums[i]));
For the first element, we initialize the prefix OR with the value of the first element.
5 : Subsequent Prefix OR Values
else prefixor.push_back(((1LL*prefixor.back()) | (1LL*nums[i])));
For subsequent elements, the prefix OR is calculated by performing a bitwise OR with the previous prefix OR value.
6 : Suffix OR Vector Initialization
vector<long long>suffixor;
A vector 'suffixor' is initialized to store the cumulative OR values from the end of the array.
7 : Suffix OR Calculation Loop
for(int i = nums.size() - 1; i >= 0; i--)
A loop iterates through 'nums' in reverse to calculate the suffix OR values.
8 : First Suffix OR Value
if(i == (nums.size()-1)) suffixor.push_back((1LL * nums[i]));
For the last element, we initialize the suffix OR with the value of the last element.
9 : Subsequent Suffix OR Values
else suffixor.push_back(((1LL*suffixor.back()) | (1LL*nums[i])));
For subsequent elements, the suffix OR is calculated by performing a bitwise OR with the next suffix OR value.
10 : Reverse Suffix OR
reverse(suffixor.begin(),suffixor.end());
The suffix OR vector is reversed so that it represents cumulative OR values from the start of the array.
11 : Result Initialization
long long ans = 0;
The variable 'ans' is initialized to 0, which will store the maximum OR value found.
12 : Main Calculation Loop
for(int i = 0 ; i < nums.size() ; i++)
A loop is initiated to calculate the OR values for each element and its neighbors.
13 : Left Value Calculation
long long int left = 0;
The variable 'left' stores the prefix OR value of the element's left neighbor.
14 : Self Value Calculation
long long int self;
The variable 'self' stores the OR value of the current element shifted by k bits.
15 : Right Value Calculation
long long int right = 0;
The variable 'right' stores the suffix OR value of the element's right neighbor.
16 : Left Value Assignment
if((i-1) >= 0)
Check if there is a left neighbor (i.e., i > 0).
17 : Left Assignment
left = prefixor[i-1];
Assign the prefix OR value of the left neighbor.
18 : Self Calculation
self = (nums[i] * pow(2,k));
Calculate the self value by shifting the current element by k bits.
19 : Right Value Assignment
if((i+1) <= nums.size()-1)
Check if there is a right neighbor (i.e., i < nums.size() - 1).
20 : Right Assignment
right = suffixor[i+1];
Assign the suffix OR value of the right neighbor.
21 : Maximum OR Update
ans = max(ans , left | self | right);
Update the 'ans' variable with the maximum OR value found.
22 : Return Result
return ans;
Return the maximum OR value calculated.
Best Case: O(n)
Average Case: O(n * k)
Worst Case: O(n * k)
Description: We iterate through the array and perform operations on each element. The worst-case time complexity occurs when we apply up to `k` operations for each element, resulting in O(n * k).
Best Case: O(n)
Worst Case: O(n)
Description: We use additional space to store the prefix and suffix ORs, which requires O(n) space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus