Unique Number I

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find element appearing odd number of times in array where all others appear even times. XOR.

Algorithm

1XOR all elements. Elements appearing even times cancel. Result is the unique element.

Common Pitfalls

•Same as LC 136. XOR of n^n = 0. Single XOR pass O(n) O(1).

Unique Number I.java

Java

// Approach: XOR all elements. Duplicate elements cancel; the unique element remains.
// Time: O(n) Space: O(1)
class Solution {
    public int findUnique(int[] arr) {
        // code here
        int uniqueVal = 0;

        for (int val : arr)
            uniqueVal ^= val;

        return uniqueVal;
    }
}

Was this solution helpful?