XOR can be very useful in cyclic and repeating structures because of one key property:

A tiled cycle cancels itself by parity alone — no scanning required:

                        1
                        cycle c = [1..k], array = c tiled m times
                      
                        2
                        x = 0; for v in array: x ^= v
                      
                        3
                        # pairs (c[i] appears m times)
                      
                        4
                        # m even → each value cancels → 0
                      
                        5
                        # m odd  → x == XOR of one cycle copy
                      

XOR depends on parity — values repeated an even number of times cancel, while values repeated an odd number of times remain.

The important correction is:

A cycle does not automatically produce XOR = 0.
The XOR is zero only when every value appears an even number of times.

Mental Trigger

Cycle + repetition + parity → think XOR

Ask:

1. How many times does each value repeat?
2. Is the repetition count even or odd?
3. Can I separate full cycles from the remaining portion?

1. XOR Cancellation in Repeated Cycles

XOR has these properties:

a ^ a = 0
a ^ 0 = a

Therefore:

a ^ b ^ c ^ a ^ b ^ c

becomes:

(a ^ a) ^ (b ^ b) ^ (c ^ c)
= 0

But:

a ^ b ^ c

does not generally equal 0.

Key Rule

Full repetition cancels only when the number of repetitions is even.

For example:

A ^ A = 0
A ^ A ^ A = A
A ^ A ^ A ^ A = 0

Pattern Table

2. XOR of a Repeated Array

Suppose:

arr = [1, 2, 3]

Its XOR is:

cycleXOR = 1 ^ 2 ^ 3

If the array repeats:

[1,2,3,1,2,3]

then:

cycleXOR ^ cycleXOR = 0

If it repeats three times:

[1,2,3,1,2,3,1,2,3]

then:

cycleXOR ^ cycleXOR ^ cycleXOR
= cycleXOR

Therefore:

Repeated cycle XOR depends on whether the number of complete repetitions is even or odd.

Java Code

public int repeatedCycleXOR(int[] arr, long repetitions) {
    int cycleXOR = 0;

    for (int num : arr) {
        cycleXOR ^= num;
    }

    return (repetitions % 2 == 0) ? 0 : cycleXOR;
}

def repeated_cycle_xor(arr, repetitions):
    cycle_xor = 0

    for num in arr:
        cycle_xor ^= num

    return 0 if repetitions % 2 == 0 else cycle_xor

int repeatedCycleXOR(vector<int>& arr, long long repetitions) {
    int cycleXOR = 0;

    for (int num : arr) {
        cycleXOR ^= num;
    }

    return (repetitions % 2 == 0) ? 0 : cycleXOR;
}

function repeatedCycleXOR(arr, repetitions) {
  let cycleXOR = 0;

  for (const num of arr) {
    cycleXOR ^= num;
  }

  return repetitions % 2 === 0 ? 0 : cycleXOR;
}

Complexity

Time:  O(n)
Space: O(1)

Instead of processing n × repetitions elements, we calculate the cycle once.

3. Circular Array XOR

A circular array allows indices to wrap around.

For:

arr = [1, 2, 3, 4]

the sequence becomes:

1, 2, 3, 4, 1, 2, 3, 4, ...

The wrapped index is:

i % n

Java Code

public int circularRangeXOR(int[] arr, int l, int r) {
    int n = arr.length;
    int result = 0;

    for (int i = l; i <= r; i++) {
        result ^= arr[i % n];
    }

    return result;
}

def circular_range_xor(arr, l, r):
    n = len(arr)
    result = 0

    for i in range(l, r + 1):
        result ^= arr[i % n]

    return result

int circularRangeXOR(vector<int>& arr, int l, int r) {
    int n = arr.size();
    int result = 0;

    for (int i = l; i <= r; i++) {
        result ^= arr[i % n];
    }

    return result;
}

function circularRangeXOR(arr, l, r) {
  const n = arr.length;
  let result = 0;

  for (let i = l; i <= r; i++) {
    result ^= arr[i % n];
  }

  return result;
}

Example

arr = [1, 2, 3]

indices:
0 → 1
1 → 2
2 → 3
3 → 1
4 → 2
5 → 3

because:

3 % 3 = 0
4 % 3 = 1
5 % 3 = 2

Circular array = normal array + modulo indexing.

4. Full Cycles + Remainder

For large circular ranges, don’t process every element individually.

Suppose the array length is n and the query contains:

k complete cycles + remainder

Let:

cycleXOR = arr[0] ^ arr[1] ^ ... ^ arr[n-1]

Then:

if k is even:
    full-cycle contribution = 0

if k is odd:
    full-cycle contribution = cycleXOR

After that, process only the remaining elements.

Mental Model

Large circular range
        ↓
Complete cycles + remainder
        ↓
Even cycles → cancel
Odd cycles  → cycleXOR
        ↓
Process remainder

5. Prefix XOR on Repeating Data

For a repeated sequence:

arr[i % n]

we can define:

prefix[i] = prefix[i - 1] ^ arr[i % n]

This allows us to reason about XOR over a finite prefix of the infinite repeating sequence.

However, for very large ranges, explicitly constructing this prefix is unnecessary.

Instead:

Calculate the XOR contribution of complete cycles using parity, then calculate the remainder.

6. XOR Graph Cycles

This is a different but important use of XOR.

Suppose graph edges represent constraints:

x[u] ^ x[v] = w

We can assign each node an XOR value relative to a starting node.

For example:

x[A] = 0

x[A] ^ x[B] = 5
→ x[B] = 5

Then if:

x[B] ^ x[C] = 7

we get:

x[C] = x[B] ^ 7
     = 5 ^ 7

Cycle Consistency

Suppose we eventually return to a node.

The constraints must agree with the value already assigned to that node.

If a new path implies:

x[v] = 10

but we previously established:

x[v] = 12

then the constraints are inconsistent.

Important Insight

XOR graph problems use relative XOR values to detect contradictory constraints.

This is more precise than saying “XOR detects cycles.”

7. XOR Distance / Potential

A useful graph representation is:

xorTo[v] = XOR value from source to v

For an edge:

u --w--> v

the relationship is:

xorTo[v] = xorTo[u] ^ w

When visiting an already-known node:

int expected = xorTo[u] ^ w;

If:

xorTo[v] != expected

then the graph contains an inconsistent XOR constraint.

8. XOR and Cycle Parity

The fundamental rule is:

x ^ x = 0

So if a cycle causes the same contribution to appear twice, those contributions cancel.

For example:

a ^ b ^ c ^ a ^ b ^ c

gives:

0

But:

a ^ b ^ c ^ a ^ b

gives:

c

because c appears only once.

Therefore:

XOR over a cycle is determined by the parity of the contributions.

Pattern Evolution

Basic XOR
    ↓
XOR Cancellation
    ↓
Repeated Patterns
    ↓
Circular Arrays + Modulo
    ↓
Full Cycles + Remainder
    ↓
XOR Graph Constraints
    ↓
Cycle Consistency Checking

Visual Intuition

Think of XOR as a parity counter:

So:

even → disappears
odd  → survives

Common Mistakes

Assuming every full cycle XOR is zero

Wrong:

a ^ b ^ c = 0

Not necessarily.

Correct:

cycle repeated twice → 0
cycle repeated three times → cycleXOR

Forgetting modulo for circular arrays

Wrong:

arr[i]

Correct:

arr[i % n]

Processing huge repetitions one by one

Instead of:

for (long i = 0; i < repetitions; i++) {
    for (int num : arr) {
        xor ^= num;
    }
}

calculate:

cycleXOR once
+
use repetition parity

Confusing cycle detection with XOR cancellation

XOR itself does not tell you that a graph contains a cycle.

For graph problems, use:

• DFS/BFS
• visited arrays
• DSU

and use XOR to verify constraint consistency.

Recognition Cheat Sheet