Single Number III - Practice Coding Problems

Single Number III - Problem

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

You can return the answer in any order.

Constraints: You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1,3,2,5]

› Output: [3,5]

💡 Note: Numbers 1 and 2 each appear twice, while 3 and 5 each appear only once. Return the two unique numbers in any order.

Example 2 — Different Numbers

$ Input: nums = [-1,0]

› Output: [-1,0]

💡 Note: Both numbers appear only once. This is the minimum case with exactly 2 elements.

Example 3 — Larger Array

$ Input: nums = [0,1,0,2,2,3]

› Output: [1,3]

💡 Note: Numbers 0 and 2 appear twice each. Numbers 1 and 3 appear only once.

Constraints

2 ≤ nums.length ≤ 3 × 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
Each integer appears exactly twice except for two integers that appear only once

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with exactly two numbers appearing once, others twice

XOR Magic

Use XOR properties to mathematically separate the unique numbers

Result

Return the two unique numbers in any order

Key Takeaway

🎯 Key Insight: XOR has the perfect property that a⊕a=0, so duplicates cancel out, leaving us with just the XOR of our two unique numbers.

Asked in

A Amazon 15 G Google 12 M Microsoft 8 🍎 Apple 6

The optimal solution uses bit manipulation with XOR properties. Key insight: XOR all numbers to get a⊕b, find any differing bit, then split array into two groups and XOR each group separately. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Frequency Count	O(n)	O(n)	Use hash map to count frequencies, then find elements with count 1
Brute Force - Count Occurrences	O(n²)	O(1)	Check each number against all others to count occurrences
Optimal - Bit Manipulation with XOR	O(n)	O(1)	Use XOR properties to separate the two unique numbers mathematically

Hash Map - Frequency Count — Algorithm Steps

Build frequency map counting all numbers
Iterate through map to find numbers with count 1
Return the two numbers with frequency 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Count frequency of each number

Find Singles

Extract numbers with count = 1

Result

Return the two unique numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10000

typedef struct {
    int key;
    int count;
} FreqEntry;

int* solution(int* nums, int numsSize, int* returnSize) {
    FreqEntry freq[MAX_SIZE];
    int freqSize = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < freqSize; j++) {
            if (freq[j].key == nums[i]) {
                freq[j].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            freq[freqSize].key = nums[i];
            freq[freqSize].count = 1;
            freqSize++;
        }
    }
    
    // Find numbers with frequency 1
    int* result = malloc(2 * sizeof(int));
    int resultIdx = 0;
    
    for (int i = 0; i < freqSize; i++) {
        if (freq[i].count == 1) {
            result[resultIdx++] = freq[i].key;
        }
    }
    
    *returnSize = resultIdx;
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3,4] format
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != '\r') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array: one to build map, one to find results

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequency for each unique number

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler