What is the brute force approach and complexity for Single Number III?

For each value, scan the array and keep it when its count is 1 with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Single Number III?

XOR everything to get a ^ b, pick one set bit, and XOR each group split by that bit with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Single Number III?

Look for key signals in the prompt: "exactly two elements appear once" indicates One XOR gives a mix of the two (a ^ b), not a single answer. We need a way to split them.; "linear time, constant extra space" indicates Two passes with a few variables. No hash map.; "return the two values in any order" indicates The split does not care about order, so [a, b] and [b, a] are both fine..

Single Number III

Medium·LeetCode #260 Pro OnlySlight Variation

LeetCode

Problem Statement

You get an array nums. Every value in it appears twice, except for two values that each appear only once. Return those two values, in any order.

Your solution must run in linear time and use constant extra space.

Input

An integer array nums with at least two values. Exactly two values appear once, and every other value appears twice.

Output

The two values that appear exactly once, in any order.

Example 1

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

Output: [3, 5]

1 and 2 each appear twice. 3 and 5 appear once, so they are the answer. [5, 3] is also accepted.

Example 2

Input: nums = [-1, 0]

Output: [-1, 0]

Both values appear once. Negative numbers are allowed.

Example 3

Input: nums = [0, 1]

Output: [1, 0]

The same two values in the other order, which is also correct.

Constraints

• 2 ≤ nums.length ≤ 3 · 10^4
• −2^31 ≤ nums[i] ≤ 2^31 − 1
• Every value appears twice, except exactly two values that appear once.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“exactly two elements appear once”

→ One XOR gives a mix of the two (a ^ b), not a single answer. We need a way to split them.

“linear time, constant extra space”

→ Two passes with a few variables. No hash map.

“return the two values in any order”

→ The split does not care about order, so [a, b] and [b, a] are both fine.

Approach Complexity Ladder

Brute Force — count each value with a loopO(N²)O(1)

For each value, scan the array and keep it when its count is 1

Better — count with a hash mapO(N)O(N)

Count every value once in a hash map, then return the values with count 1

Optimal — split by one differing bit, then XOR each groupO(N)O(1)

XOR everything to get a ^ b, pick one set bit, and XOR each group split by that bit

Brute Force Intuition

For each value in nums, scan the whole array and count how many times it appears. Keep every value whose count is exactly 1. Those are the two answers.

Recognition rule for this sub-pattern:

x ^ x = 0 and x ^ 0 = x, so XOR-ing everything cancels the pairs.

Remember this · Bit Manipulation

Trigger

"Every element appears twice except…", power of two, counting set bits, subsets as bitmasks, O(1) space tricks.

Think

What happens to this problem if I look at each bit separately?

Key question

Which bit operation (XOR, AND, OR, shift) cancels or isolates what I need?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture