Replace with XOR of Adjacent

Time: O(n)

Space: O(1)

Intuition

Each output element depends only on the current original value and the next original value, so the array can be rewritten in place from left to right as long as we preserve the previous original value in a temporary variable. That makes the transformation linear time and constant extra space.

Algorithm

1Store the original arr[0] in prev.
2For each i from 0 to n-2:
3 Save arr[i] into temp before overwriting it.
4 Set arr[i] = prev XOR arr[i+1].
5 Update prev = temp so the next step still knows the original current value.
6Set arr[n-1] = arr[n-1] XOR prev for the last position.

Example Walkthrough

Input: arr = [1, 2, 3, 4]

1.prev = 1.
2.i=0 -> arr[0] = 1 XOR 2 = 3, prev stays original 1 for next step.
3.i=1 -> arr[1] = 1 XOR 3 = 2, prev becomes original 2.
4.i=2 -> arr[2] = 2 XOR 4 = 6, then last element becomes 4 XOR 3 = 7.

Output: [3, 2, 6, 7]

Common Pitfalls

•Do not read from the overwritten array values when advancing; always preserve the original current value first.
•The last element uses the final saved previous original value, not the updated prefix.
•No extra array should be allocated; the point of the task is in-place transformation.

Replace with XOR of Adjacent.java

Java


// Approach: Sweep left to right, overwriting each position with XOR of the current element and the next one.
// Preserve the previous original value in a temporary variable so the chain can continue without extra memory.
// The final element is handled separately using the last saved original value.
// Time: O(n) Space: O(1)

class Solution {

    public void replaceElements(int[] arr) {
        int n = arr.length;
        int prev = arr[0];
        for (int i = 0; i < n - 1; i++) {
            int temp = arr[i];
            arr[i] = prev ^ arr[i + 1];
            prev = temp;
        }
        arr[n - 1] = arr[n - 1] ^ prev;
    }
}

Was this solution helpful?