Game of XOR

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

XOR of XOR of all subarrays. Mathematical: element at index i contributes based on count of subarrays containing it.

Algorithm

1Element arr[i] appears in (i+1)*(n-i) subarrays. If this count is odd: XOR it into result.

Common Pitfalls

•Count occurrences: arr[i] is in subarrays starting at 0..i ending at i..n-1. Multiply counts.

Game of XOR.java

Java

// Approach: Observe XOR pattern. XOR of a range [1..n] follows a 4-cycle pattern. Use prefix XOR.
// Time: O(n) Space: O(1)
class Solution {
    public int subarrayXor(int[] arr) {
        int n = arr.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            long freq = (long) (i + 1) * (n - i);
            if (freq % 2 != 0)
                total ^= arr[i];
        }
        return total;
    }
}

Was this solution helpful?