Single Number - Practice Coding Problems

Single Number - Problem

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Numbers 2 and 1 each appear twice, while 3 appears only once. The single number is 3.

Example 2 — Single Element

$ Input: nums = [4,1,2,1,2]

› Output: 4

💡 Note: Numbers 1 and 2 each appear twice, while 4 appears only once. The single number is 4.

Example 3 — Minimum Size

$ Input: nums = [1]

› Output: 1

💡 Note: Array has only one element, so 1 is the single number that doesn't appear twice.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
Each element in the array appears twice except for one element which appears only once

Visualization

Tap to expand

Understanding the Visualization

Input

Array where every element appears twice except one

Process

Use XOR to cancel out identical pairs

Output

The single number that doesn't have a pair

Key Takeaway

🎯 Key Insight: XOR all elements - identical pairs cancel out (a ⊕ a = 0), leaving only the single number

Asked in

G Google 42 a Amazon 38 M Microsoft 31 A Apple 28 f Facebook 25

The key insight is using XOR bit manipulation where identical numbers cancel out (a ⊕ a = 0). Best approach is XOR all elements - pairs disappear leaving only the single number. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ XOR Bit Manipulation (Optimal)	O(n)	O(1)	Use XOR property where identical numbers cancel out, leaving only the single number
Hash Map - Frequency Count	O(n)	O(n)	Count frequency of each element using a hash map
Brute Force - Count Each Element	O(n²)	O(1)	For each element, count its occurrences in the entire array

XOR Bit Manipulation (Optimal) — Algorithm Steps

Initialize result = 0
XOR result with each number in array
All pairs cancel out (a ⊕ a = 0), leaving only single number

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with result = 0

XOR All

XOR each number: 0⊕2⊕1⊕2⊕3⊕1 = 3

Pairs Cancel

2⊕2=0, 1⊕1=0, leaving only 3

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int result = 0;
    for (int i = 0; i < numsSize; i++) {
        result ^= nums[i];
    }
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, XOR operation is O(1)

✓ Linear Growth

Space Complexity

O(1)

Only using one variable to store result, no extra data structures

✓ Linear Space

336.8K Views

High Frequency

~15 min Avg. Time

8.4K 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

XOR Bit Manipulation (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler