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 XOR After Operations

Number: 2402

Difficulty: Medium

Paid? No

Companies: American Express

Problem Description

Given a 0-indexed integer array nums, you are allowed to perform an operation any number of times. In one operation, you choose any non-negative integer x and an index i, and update nums[i] to be equal to nums[i] AND (nums[i] XOR x) (where AND and XOR denote bitwise operations). Your goal is to maximize the bitwise XOR of all elements in nums after applying the operations.

Key Insights

  • Each element’s bits can only be turned off, not turned on; you can selectively remove 1 bits.
  • For each element, every bit originally set (i.e. equal to 1) can be either kept or cleared.
  • This means that for each bit position, if at least one element originally had that bit set, you can choose to keep that bit in the overall computation.
  • Therefore, the maximum bitwise XOR that can be achieved is simply the bitwise OR of all elements in the array.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in nums (we iterate through the array once).
Space Complexity: O(1) (we use a constant amount of extra space).

Solution

The key observation is that the given operation allows you to decide, for each element, which of its originally set bits to keep. Since no new bits can be introduced, the optimal strategy is to ensure that for every bit that occurs in at least one element, that bit contributes to the final XOR.
Thus, the maximum possible bitwise XOR of the array equals the bitwise OR of all the numbers in nums.
The solution involves iterating through the array, accumulating the OR of every element, and then returning the result.

Code Solutions

# Function to compute the maximum XOR after operations
def maximumXORAfterOperations(nums):
    # Initialize the result to 0
    max_xor = 0
    # Iterate over each number in the list
    for num in nums:
        # Update max_xor with bitwise OR to collect every set bit from nums
        max_xor |= num  # Bitwise OR: includes bits from num that are not yet set in max_xor
    # Return the computed result
    return max_xor

# Example usage:
nums = [3, 2, 4, 6]
print(maximumXORAfterOperations(nums))  # Expected output: 7
← Back to All Questions