Unique Number III

JavaView on GFG

Time: O(32n)

Space: O(1)

Problem Overview

Find element appearing once when all others appear three times.

Intuition

Find element appearing once when all others appear three times. Bit counting modulo 3.

Algorithm

1For each bit position: count how many numbers have this bit set. If count % 3 != 0: unique number has this bit.

Common Pitfalls

• Same as LC 137. 32-bit scan, each bit modulo 3. O(32n) = O(n).

Unique Number III.java

Java

// Approach: Bit counting modulo 3. For each bit position, count total 1s; the unique element has count % 3 != 0.
// Time: O(32n) Space: O(1)
class Solution {
    public int getSingle(int[] arr) {
        int res = 0;

        for (int i = 0; i < 32; i++) {
            int bitsum = 0;
            for (int num : arr) {
                if (((num >> i) & 1) != 0)
                    bitsum++;
            }
            
            if (bitsum % 3 != 0)
                res |= (1 << i);
        }
        return res;
    }
}

Was this solution helpful?