Find the Xor-Beauty of Array

Medium
727.

Find the Xor-Beauty of Array

Find the Xor-Beauty of Array is a medium coding problem on arrays, math and bit manipulation, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var xorBeauty = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Xor-Beauty of Array — Problem & Solution

Find the Xor-Beauty of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find the Xor-Beauty of Array is a medium coding problem on arrays, math and bit manipulation, asked in Amazon and Google interviews.

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

Hints for Find the Xor-Beauty of Array

  1. Hint 1

    Work one bit at a time and count how many triples have that bit set in their effective value.

  2. Hint 2

    For a fixed bit, let c be how many elements have it. The count of triples is c(2n - c)… work out its parity.

  3. Hint 3

    That parity turns out to match the parity of c itself, which means the answer is simply the XOR of the array.

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

Java

public static int xorBeauty(int[] nums) {
    int out = 0;
    for (int x : nums) out ^= x;
    return out;
}

C++

int xorBeauty(vector<int>& nums) {
    int out = 0;
    for (int x : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Bit Manipulation