Single Number

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find element that appears once when all others appear twice.

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?