Problem Statement

Given a integer array nums of length n (0-indexed) and an integer k, you may perform the following operation at most k times:

• Select any element and multiply it by 2

Return the maximum value of nums[0] | nums[1] | ... | nums[n - 1], where a | b denotes the bitwise OR operation.

Examples:

Example 1:

Input: nums = [12,9], k = 1
Output: 30

Multiplying the element at index 1 by 2 produces [12, 18]. The bitwise OR of 12 and 18 equals 30.

Example 2:

Input: nums = [8,1,2], k = 2
Output: 35

Multiplying the element at index 0 twice yields [32, 1, 2]. The bitwise OR of 32, 1, and 2 equals 35.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= 15

Solution Strategy

The key insight is that all k operations should be applied to a single element. Each multiplication by 2 corresponds to a left shift by one bit position in binary representation. By repeatedly doubling the same number, we push its highest set bit further left, maximizing the overall OR result across all array elements.

Note that the result may exceed the int range, so long should be used for the return type.

Approach 1: Prefix and Suffix OR Arrays

For each element, we need to compute the OR of all other elements plus the current element shifted left by k bits. To avoid redundant calculations, precompute prefix and suffix OR values:

• prefix[i]: bitwise OR of elements from index 0 to i-1
• suffix[i]: bitwise OR of elmeents from index i+1 to n-1

public long maximumOr(int[] nums, int k) {
    int length = nums.length;
    int[] suffixOr = new int[length];
    
    // Compute suffix OR values from right to left
    for (int i = length - 1; i >= 1; i--) {
        suffixOr[i - 1] = suffixOr[i] | nums[i];
    }
    
    long result = 0;
    long prefixOr = 0;
    
    for (int i = 0; i < length; i++) {
        long shiftedValue = (long) nums[i] << k;
        long currentOr = prefixOr | shiftedValue | suffixOr[i];
        result = Math.max(result, currentOr);
        prefixOr |= nums[i];
    }
    
    return result;
}

Approach 2: Space-Optimized Solution

We can eliminate the auxiliary arrays by leveraging XOR and tracking bits that appear in multiple numbers.

First, compute the total OR of all elements and identify bits that are set in at least two different numbers. These "fixed" bits will remain set in the final result regardless of which element we shift.

public long maximumOr(int[] nums, int k) {
    long totalOr = 0;
    long commonBits = 0;
    
    // Identify bits that appear in multiple numbers
    for (int num : nums) {
        commonBits |= totalOr & num;
        totalOr |= num;
    }
    
    long answer = 0;
    
    for (int num : nums) {
        // Remove current number's contribution, restore common bits
        long othersOr = (totalOr ^ num) | commonBits;
        long candidate = othersOr | ((long) num << k);
        answer = Math.max(answer, candidate);
    }
    
    return answer;
}

The optimization works because:

1. Using XOR removes the current number's bits from the total OR
2. The commonBits value tracks any bit posision where at least two numbers have a 1
3. Since these bits are guaranteed to be 1 in the final result, we restore them after the XOR operation