Get started

Find the Xor-Beauty of Array — Medium Problem & Solution

The effective value of an ordered triple (i, j, k) is ((nums[i] OR nums[j]) AND nums[k]). Indices may repeat.

Problem statement

The effective value of an ordered triple (i, j, k) is ((nums[i] OR nums[j]) AND nums[k]). Indices may repeat.

The xor-beauty of the array is the XOR of the effective values over all n³ triples. Return it.

Example 1

Input: nums = [1,4]
Output: 5
Explanation: The eight triples XOR down to 5, which is also 1 XOR 4.

Example 2

Input: nums = [15,45,20,2,34,35,5,44,32,30]
Output: 34

Example 3

Input: nums = [7]
Output: 7

Constraints

  • 1 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000000

How to solve Find the Xor-Beauty of Array

Count, per bit, how many triples contribute it — then only the parity of that count matters, because XOR cancels in pairs. The parity works out to the parity of the number of elements carrying the bit, so the whole expression collapses to the XOR of the array.

Approach

  1. Return the XOR of every element of nums.

Why it works

Fix a bit and let c be the number of elements that have it. A triple contributes that bit when nums[k] has it and at least one of nums[i], nums[j] does — that is c · (n² - (n - c)²) = c · c · (2n - c). Modulo 2 this reduces to c, since c·c ≡ c and 2n - c ≡ c. So the bit survives exactly when an odd number of elements carry it, which is the definition of XOR.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Enumerating triples is 10^15 operations at the stated limits.
  • The result is not the OR — the parity argument is what makes it the XOR.

Reference solution

Python

from typing import List

def xorBeauty(nums: List[int]) -> int:
    out = 0
    for x in nums:
        out ^= x
    return out

JavaScript

var xorBeauty = function(nums) {
    var out = 0;
    for (var i = 0; i < nums.length; i++) out ^= nums[i];
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue