Single Number

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find element that appears once when all others appear twice. XOR of all elements cancels pairs.

Algorithm

1result = 0. For each num: result ^= num. Return result.

Common Pitfalls

•XOR is self-inverse: a^a=0, a^0=a. Same as LC 136. O(n) time, O(1) space.

Single Number.java

Java

// Approach: XOR all elements. Paired elements cancel; the unpaired element remains.
// Time: O(n) Space: O(1)
class Solution {
    int getSingle(int arr[]) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++)
            ans = ans ^ arr[i];

        return ans;
    }
}

Was this solution helpful?