Single Number II - Practice Coding Problems

Single Number II - Problem

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

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

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Element 2 appears 3 times, element 3 appears 1 time. Return 3.

Example 2 — Larger Array

$ Input: nums = [0,1,0,1,0,1,99]

› Output: 99

💡 Note: Elements 0 and 1 each appear 3 times, element 99 appears 1 time. Return 99.

Example 3 — Single Element

$ Input: nums = [5]

› Output: 5

💡 Note: Only one element in array, it appears once. Return 5.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
-2³¹ ≤ nums[i] ≤ 2³¹ - 1
Each element in the array appears exactly three times except for one element which appears exactly once.

Visualization

Tap to expand

Understanding the Visualization

Input

Array where all elements appear 3 times except one

Process

Use bit manipulation to track occurrences

Output

Return the single unique element

Key Takeaway

🎯 Key Insight: Use bit manipulation to count occurrences modulo 3, allowing constant space solution

Asked in

G Google 25 M Microsoft 20 a Amazon 18 Apple 15

The key insight is to use bit manipulation to count occurrences modulo 3. The optimal digital counter approach uses two variables to track bits that appear once or twice, automatically resetting when they appear three times. 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 element with count 1
Bit Manipulation - Digital Circuit	O(n)	O(1)	Use two variables to track bit occurrences modulo 3
Brute Force - Nested Loop	O(n²)	O(1)	For each element, count its occurrences in the entire array

Hash Map - Frequency Count — Algorithm Steps

Step 1: Count frequency of each element in hash map
Step 2: Iterate through map to find element with count = 1
Step 3: Return that element

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Map

Count each element's frequency

Find Single

Look for frequency = 1

Return Result

Return the unique element

Code -

solution.c — C

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

#define MAX_NUMS 10000

typedef struct {
    int key;
    int value;
} Pair;

int solution(int* nums, int numsSize) {
    Pair count[MAX_NUMS];
    int mapSize = 0;
    
    // Count frequencies
    for (int i = 0; i < numsSize; i++) {
        int found = 0;
        for (int j = 0; j < mapSize; j++) {
            if (count[j].key == nums[i]) {
                count[j].value++;
                found = 1;
                break;
            }
        }
        if (!found) {
            count[mapSize].key = nums[i];
            count[mapSize].value = 1;
            mapSize++;
        }
    }
    
    // Find element with frequency 1
    for (int i = 0; i < mapSize; i++) {
        if (count[i].value == 1) {
            return count[i].key;
        }
    }
    
    return 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[10000];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array - one to count, one to find

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n/3 unique elements

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

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