Find Only Repetitive Element from 1 to n-1

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Array of size n with values 1 to n-1, one repeated. Find it using XOR or sum formula.

Algorithm

1Sum formula: ans = sum(arr) - n*(n-1)/2.
2XOR: XOR all elements with 1..n-1. Result is the duplicate.

Common Pitfalls

•Sum overflow: use long. XOR method is O(n) O(1) with no overflow risk.

Find Only Repetitive Element from 1 to n-1.java

Java

// Approach: XOR all indices 1..n with all array elements. The repeated element XORs itself twice.
// Alternatively: sum formula or sign-flip marking.
// Time: O(n) Space: O(1)
class Solution {
    public int findDuplicate(int[] arr) {
        int xorr = 0;
        for (int i = 0; i < arr.length; i++)
            xorr ^= arr[i];

        for (int i = 1; i < arr.length; i++)
            xorr ^= i;

        return xorr;
    }
}

Was this solution helpful?