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

Find Xor-Beauty of Array

Number: 2621

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums, the effective value of a triplet (i, j, k) is defined as ((nums[i] | nums[j]) & nums[k]). The xor-beauty of the array is the XOR of the effective values over all possible triplets (i, j, k). You need to compute and return this xor-beauty.

Key Insights

  • The operation is defined bitwise, allowing consideration of each bit independently.
  • When analyzing each bit, it turns out that the contribution from the OR and AND operations cancels out in such a way that the final XOR is simply the XOR of all nums elements.
  • A careful bit-by-bit analysis reveals that for each bit position, the parity of set bits in the final result coincides exactly with the parity of the set bits in the XOR of the entire array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in nums. Space Complexity: O(1), since only a constant amount of extra space is used.

Solution

The key observation is that despite the apparent complexity of triple nesting (i,j,k), each bit of the final result depends solely on whether that bit is set in an odd number of the input numbers. Through bitwise manipulation and parity analysis, we reduce the original problem to computing the XOR of all the elements in the array. This can be done in one pass with a simple loop.

  • Data Structure: No additional data structure is required. We just use a variable to store the cumulative XOR.
  • Algorithm: Iterate through the array and update the cumulative XOR with every element.
  • Trick/Insight: Realize that the bit interactions in the expression ((a | b) & c) cause every bit's contribution to simplify to merely the bit from c if it appears an odd number of times overall. Therefore, the final answer is simply the XOR of all elements.

Code Solutions

# Python solution
# Initialize a result variable to hold cumulative XOR of all elements.
def xorBeauty(nums):
    result = 0  # Holds the cumulative XOR result.
    for num in nums:  # Iterate over each number in nums
        result ^= num  # XOR the current number with the result
    return result

# Example usage:
nums_example = [1, 4]
print(xorBeauty(nums_example))
← Back to All Questions