Scale Engineer

Maximum OR

Med
#2429Time: O(N^2), where N is the number of elements in `nums`. The outer loop runs N times, and for each iteration, the inner loop also runs N times to compute the total OR.Space: O(1), as we only use a few variables to store the intermediate and final results, not dependent on the input size.1 company
Patterns
GreedyBit ManipulationPrefix Sum
Data structures
Array
Companies
DE Shaw

Prompt

You are given a 0-indexed integer array nums of length n and an integer k. In an operation, you can choose an element and multiply it by 2.

Return the maximum possible value of nums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at most k times.

Note that a | b denotes the bitwise or between two integers a and b.

 

Example 1:

Input: nums = [12,9], k = 1
Output: 30
Explanation: If we apply the operation to index 1, our new array nums will be equal to [12,18]. Thus, we return the bitwise or of 12 and 18, which is 30.

Example 2:

Input: nums = [8,1,2], k = 2
Output: 35
Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return 32|1|2 = 35.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 15

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each element of the array nums. For each element nums[i], it calculates the potential maximum OR value that can be achieved if all k multiplication operations are applied to nums[i]. The overall maximum value across all choices of i is the answer.

Algorithm

  1. Initialize a variable maxOrValue to store the maximum OR value found so far, setting it to 0.
  2. Iterate through each element nums[i] in the input array nums using an outer loop from i = 0 to n-1.
  3. For each nums[i], this element is the candidate to apply all k operations on.
  4. Calculate the value of nums[i] after k left shifts: shiftedNum = (long)nums[i] << k. Note the cast to long to prevent potential overflow.
  5. Initialize a currentOrValue with shiftedNum.
  6. Start an inner loop to iterate through all elements nums[j] from j = 0 to n-1.
  7. Inside the inner loop, if j is not equal to i, calculate the bitwise OR of currentOrValue with nums[j]: currentOrValue |= nums[j].
  8. After the inner loop completes, currentOrValue holds the total bitwise OR if nums[i] was the chosen element. Update the overall maximum: maxOrValue = Math.max(maxOrValue, currentOrValue).
  9. After the outer loop finishes, maxOrValue will contain the maximum possible OR value. Return maxOrValue.

Walkthrough

The core idea is based on the observation that to maximize the bitwise OR, we should aim to set the most significant bits to 1. Applying k multiplications by 2 to a number x is equivalent to a left bit shift x << k, which is a very effective way to set higher-order bits. It is optimal to apply all k operations to a single element rather than distributing them. This brute-force approach directly implements this idea by trying every possible element nums[i] as the target for the k operations. For each choice of nums[i], it computes the resulting total OR by iterating through the entire array again. While straightforward, this leads to a nested loop structure and quadratic time complexity.

class Solution {    public long maximumOr(int[] nums, int k) {        long maxOrValue = 0;        int n = nums.length;        for (int i = 0; i < n; i++) {            // Apply k operations to nums[i]            long shiftedNum = (long) nums[i] << k;                        // Calculate the OR with all other elements            long currentOrValue = 0;            for (int j = 0; j < n; j++) {                if (i == j) {                    currentOrValue |= shiftedNum;                } else {                    currentOrValue |= nums[j];                }            }            maxOrValue = Math.max(maxOrValue, currentOrValue);        }        return maxOrValue;    }}

Complexity

Time

O(N^2), where N is the number of elements in `nums`. The outer loop runs N times, and for each iteration, the inner loop also runs N times to compute the total OR.

Space

O(1), as we only use a few variables to store the intermediate and final results, not dependent on the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space.

Cons

  • The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5) and will result in a Time Limit Exceeded (TLE) error on most platforms.

Solutions

class Solution { public long maximumOr ( int [] nums , int k ) { int n = nums . length ; long [] suf = new long [ n + 1 ]; for ( int i = n - 1 ; i >= 0 ; -- i ) { suf [ i ] = suf [ i + 1 ] | nums [ i ]; } long ans = 0 , pre = 0 ; for ( int i = 0 ; i < n ; ++ i ) { ans = Math . max ( ans , pre | ( 1L * nums [ i ] << k ) | suf [ i + 1 ]); pre |= nums [ i ]; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem