Unique Number II

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find two elements appearing odd times, all others appear even times.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find two elements appearing odd times, all others appear even times. XOR + bit grouping.

Algorithm

1XOR all to get xor of two targets. Find a set bit. Divide into two groups by this bit. XOR each group.

Common Pitfalls

• Same as LC 260. Set bit in XOR distinguishes the two unique numbers. O(n) O(1).

Unique Number II.java

Java

// Approach: XOR all elements to get XOR of two unique numbers. Split by a set bit; XOR each group separately.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int[] singleNum(int[] nums) {
        int xxory = 0;

        for (int it : nums)
            xxory = xxory ^ it;

        int number = xxory & -xxory;
        int x = 0;
        int y = 0;
        for (int it : nums) {
            if ((it & number) != 0)
                x = x ^ it;
            else
                y = y ^ it;
        }
        List<Integer> result = new ArrayList<>();
        if (x > y) {
            result.add(y);
            result.add(x);
        } else {
            result.add(x);
            result.add(y);
        }
        
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

Was this solution helpful?