Scale Engineer

Find Xor-Beauty of Array

Med
#2307Time: O(n^3), where n is the number of elements in the `nums` array. This is because there are three nested loops, each running `n` times.Space: O(1), as we only use a constant amount of extra space for loop counters and the result variable.
Patterns
MathBit Manipulation
Data structures
Array

Prompt

You are given a 0-indexed integer array nums.

The effective value of three indices i, j, and k is defined as ((nums[i] | nums[j]) & nums[k]).

The xor-beauty of the array is the XORing of the effective values of all the possible triplets of indices (i, j, k) where 0 <= i, j, k < n.

Return the xor-beauty of nums.

Note that:

  • val1 | val2 is bitwise OR of val1 and val2.
  • val1 & val2 is bitwise AND of val1 and val2.

 

Example 1:

Input: nums = [1,4]
Output: 5
Explanation: 
The triplets and their corresponding effective values are listed below:
- (0,0,0) with effective value ((1 | 1) & 1) = 1
- (0,0,1) with effective value ((1 | 1) & 4) = 0
- (0,1,0) with effective value ((1 | 4) & 1) = 1
- (0,1,1) with effective value ((1 | 4) & 4) = 4
- (1,0,0) with effective value ((4 | 1) & 1) = 1
- (1,0,1) with effective value ((4 | 1) & 4) = 4
- (1,1,0) with effective value ((4 | 4) & 1) = 0
- (1,1,1) with effective value ((4 | 4) & 4) = 4 
Xor-beauty of array will be bitwise XOR of all beauties = 1 ^ 0 ^ 1 ^ 4 ^ 1 ^ 4 ^ 0 ^ 4 = 5.

Example 2:

The xor-beauty of the given array is 34.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach that directly implements the problem description. It iterates through all nnn possible triplets of indices (i, j, k) and calculates the effective value for each. The xor-beauty is computed by XORing all these effective values together.

Algorithm

  • Initialize a variable, xorBeauty, to 0. This will store the cumulative XOR sum.
  • Use a loop for index i from 0 to n-1, where n is the length of the nums array.
  • Inside this loop, nest another loop for index j from 0 to n-1.
  • Inside the second loop, nest a third loop for index k from 0 to n-1.
  • In the innermost loop, we have a valid triplet (i, j, k). Calculate the effective value: value = (nums[i] | nums[j]) & nums[k].
  • Update the xorBeauty by XORing it with the value: xorBeauty ^= value.
  • After the three loops have finished, xorBeauty will contain the XOR sum of all effective values, which is the desired result.

Walkthrough

This approach is a direct translation of the problem statement into code. We need to find the XOR sum of ((nums[i] | nums[j]) & nums[k]) for all possible combinations of indices i, j, and k.

class Solution {    public int xorBeauty(int[] nums) {        int n = nums.length;        int xorBeauty = 0;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                for (int k = 0; k < n; k++) {                    int effectiveValue = (nums[i] | nums[j]) & nums[k];                    xorBeauty ^= effectiveValue;                }            }        }        return xorBeauty;    }}

Complexity

Time

O(n^3), where n is the number of elements in the `nums` array. This is because there are three nested loops, each running `n` times.

Space

O(1), as we only use a constant amount of extra space for loop counters and the result variable.

Trade-offs

Pros

  • Simple to understand and implement directly from the problem statement.

Cons

  • Extremely inefficient due to its cubic time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (n up to 10^5).

Solutions

class Solution {public  int xorBeauty(int[] nums) {    int ans = 0;    for (int x : nums) {      ans ^= x;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem