We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum OR

Number: 2730

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

You are given a 0-indexed integer array nums of length n and an integer k. In one operation you can choose an element from nums and multiply it by 2 (which is equivalent to a left-shift by 1 bit). You may perform this operation at most k times. Your goal is to maximize the bitwise OR of all elements in the array. In other words, after up to k operations, maximize (nums[0] | nums[1] | ... | nums[n - 1]).

Key Insights

  • Multiplying an element by 2 is equivalent to shifting its binary representation left by 1 (i.e. multiplying by 2^1). Thus, applying the operation k times multiplies the element by 2^k.
  • The bitwise OR of the array is determined by the bits present in its elements; once a bit is set (1) in any element, it remains set in the result.
  • Since you can perform the operation on at most k elements in total, one effective strategy is to select a single element and apply all k operations on it, boosting its contribution by a factor of 2^k.
  • For each candidate element, you can compute the OR if that element is boosted while all other elements remain unchanged.
  • To obtain the OR of the entire array excluding one candidate element, you can precompute prefix OR and suffix OR arrays to efficiently combine contributions from the left and right sides.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in the array. Space Complexity: O(n) for storing the prefix and suffix OR arrays.

Solution

The approach is as follows:

  1. Compute a prefix OR array where prefix[i] is the OR of all elements from nums[0] to nums[i].
  2. Compute a suffix OR array where suffix[i] is the OR of all elements from nums[i] to nums[n-1].
  3. For each index i, calculate the OR excluding nums[i] using:
    • left_part = prefix[i - 1] (if i > 0)
    • right_part = suffix[i + 1] (if i < n - 1)
    • current_OR_excluding = left_part OR right_part (or 0 if neither exists).
  4. Boost the candidate element nums[i] by k operations, i.e., set boosted_value = nums[i] * (2^k).
  5. Calculate candidate_total = current_OR_excluding OR boosted_value.
  6. Track the maximum candidate_total over all indices.
  7. Also consider the situation in which no operations are used (i.e., the OR of the original array) – this value might be optimal when boosting does not add new bits.
  8. Return the maximum value found.

This solution leverages bit manipulation for shifting and the idea of precomputing prefix and suffix ORs to efficiently compute the OR of the array with one element omitted.

Code Solutions

# Python solution with detailed comments

def maximumOr(nums, k):
    n = len(nums)
    # Precompute prefix OR: prefix[i] is OR of nums[0] to nums[i]
    prefix = [0] * n
    prefix[0] = nums[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] | nums[i]

    # Precompute suffix OR: suffix[i] is OR of nums[i] to nums[n-1]
    suffix = [0] * n
    suffix[n-1] = nums[n-1]
    for i in range(n-2, -1, -1):
        suffix[i] = suffix[i+1] | nums[i]

    # Calculate power factor: 2^k
    multiplier = 1 << k  # equivalent to 2**k

    max_or = 0
    # Try boosting every element with all k operations
    for i in range(n):
        # Get OR of all elements except nums[i]
        left_or = prefix[i-1] if i > 0 else 0
        right_or = suffix[i+1] if i < n-1 else 0
        combined_or = left_or | right_or
        
        # Boost current number by multiplying by 2^k
        boosted_value = nums[i] * multiplier
        
        # Candidate OR after operation on nums[i]
        candidate_or = combined_or | boosted_value
        max_or = max(max_or, candidate_or)

    # Also consider no operations at all (the OR of the entire array)
    max_or = max(max_or, prefix[n-1])
    
    return max_or

# Example usage:
print(maximumOr([12, 9], 1))  # Expected output: 30
print(maximumOr([8, 1, 2], 2))  # Expected output: 35
← Back to All Questions