Run your code 2 more times to open the solutions. The idea sticks better after an attempt. Single Number in Python
2 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
Counter from collections walks the list once and maps each value to how often it appears. The answer is the one key whose count is 1. It is linear time, but the counter holds about half the list in memory.
from collections import Counter
def single_number(nums: list[int]) -> int:
counts = Counter(nums) # value -> number of copies
for value, count in counts.items():
if count == 1:
return value
return 0 # unreachable when the input follows the rules
XOR a running value with every number. A number XORed with itself is 0 and XOR is order-independent, so every pair cancels and only the lone value survives. Python's ^ works on negative integers as two's complement with unlimited width, so negatives cancel just like positives.
def single_number(nums: list[int]) -> int:
result = 0
for n in nums:
result ^= n # pairs cancel: a ^ a == 0
return result
Single Number in JavaScript
2 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
A Map counts each value in one pass; (counts.get(n) ?? 0) + 1 starts a missing key at zero. A second loop over the map's entries returns the value whose count is 1. Both loops are linear, and the map holds every distinct value.
function singleNumber(nums) {
const counts = new Map(); // value -> number of copies
for (const n of nums) counts.set(n, (counts.get(n) ?? 0) + 1);
for (const [value, count] of counts) {
if (count === 1) return value;
}
return 0; // unreachable when the input follows the rules
}
reduce folds the array into one number with ^, starting from 0. Equal values cancel (a ^ a is 0) in any order, so the lone value is all that is left. No extra memory beyond the accumulator.
function singleNumber(nums) {
return nums.reduce((acc, n) => acc ^ n, 0);
}
Single Number in TypeScript
2 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
A Map<number, number> counts every value in one pass, and a second pass over its entries returns the value seen once. Linear time, with memory for every distinct value.
function singleNumber(nums: number[]): number {
const counts = new Map<number, number>();
for (const n of nums) counts.set(n, (counts.get(n) ?? 0) + 1);
for (const [value, count] of counts) {
if (count === 1) return value;
}
return 0; // unreachable when the input follows the rules
}
XOR every number into one accumulator that starts at 0. Each pair cancels because a ^ a is 0 and the order does not matter, so the lone value is left. Constant extra space.
function singleNumber(nums: number[]): number {
let result = 0;
for (const n of nums) result ^= n; // pairs cancel
return result;
}
Single Number in Java
2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
counts.merge(n, 1, Integer::sum) inserts 1 for a new value and adds 1 to an existing count, all in one call. A second loop over entrySet() returns the key whose count is 1. Linear time; the map boxes every distinct value into an Integer.
import java.util.*;
public class Main {
static int singleNumber(int[] nums) {
HashMap<Integer, Integer> counts = HashMap.newHashMap(nums.length);
for (int n : nums) {
counts.merge(n, 1, Integer::sum);
}
for (Map.Entry<Integer, Integer> e : counts.entrySet()) {
if (e.getValue() == 1) {
return e.getKey();
}
}
return 0; // unreachable when the input follows the rules
}
}
Fold every element into result with ^=. Because a ^ a is 0, a ^ 0 is a and XOR is order-independent, the pairs cancel and the lone value remains. Java int XOR works bit by bit on the two's complement form, so negative values cancel too. No allocation at all.
import java.util.*;
public class Main {
static int singleNumber(int[] nums) {
int result = 0;
for (int n : nums) {
result ^= n; // pairs cancel
}
return result;
}
}
Single Number in Go
2 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
counts[n]++ works on a missing key because a Go map read returns the zero value, so the first copy lands at 1. A second range over the map returns the value whose count is 1. Map iteration order is random, but only one key can match, so the answer is stable.
package main
func singleNumber(nums []int) int {
counts := make(map[int]int, len(nums)) // value -> number of copies
for _, n := range nums {
counts[n]++
}
for value, count := range counts {
if count == 1 {
return value
}
}
return 0 // unreachable when the input follows the rules
}
In Go the binary ^ is XOR (the unary ^x is bitwise NOT). Folding every element into result with ^= cancels each pair, since a ^ a is 0 in any order, and leaves the lone value. No allocation.
package main
func singleNumber(nums []int) int {
result := 0
for _, n := range nums {
result ^= n // pairs cancel
}
return result
}
Single Number in C#
2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
Count each value in a Dictionary<int, int>: GetValueOrDefault returns 0 for a value not seen yet, so the first copy is stored as 1. A second loop over the pairs returns the key whose count is 1. Linear time, with memory for every distinct value.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int SingleNumber(int[] nums)
{
var counts = new Dictionary<int, int>();
foreach (int n in nums)
{
counts[n] = counts.GetValueOrDefault(n) + 1;
}
foreach (var (value, count) in counts)
{
if (count == 1) return value;
}
return 0; // unreachable when the input follows the rules
}
}
Fold every element into result with ^=. A value XORed with itself is 0 and the order does not matter, so the pairs cancel and the lone value is left. No allocation, and XOR cannot overflow.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int SingleNumber(int[] nums)
{
int result = 0;
foreach (int n in nums)
{
result ^= n; // pairs cancel
}
return result;
}
}
Single Number in C++
2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
counts[n]++ inserts a zero for a value not seen yet and then bumps it, so one line counts every value. A range-for with structured bindings walks the map and returns the key whose count is 1. reserve sizes the table up front so it does not rehash while filling.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int, int> counts;
counts.reserve(nums.size());
for (int n : nums) counts[n]++;
for (const auto& [value, count] : counts) {
if (count == 1) return value;
}
return 0; // unreachable when the input follows the rules
}
};
Fold every element into result with ^=. Pairs cancel because a ^ a is 0 in any order, and the lone value remains. Bitwise XOR on int is well defined for negative values too, and it cannot overflow.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (int n : nums) result ^= n; // pairs cancel
return result;
}
};
Single Number in C
2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
C has no built-in map, so build a small one: an open-addressing table at least twice the input's size (a power of two) holding each distinct value and its count, with a used flag per slot. One pass fills the counts, a second pass over the table finds the slot whose count is 1. The three arrays are freed before the function returns.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int singleNumber(int* nums, int numsSize) {
int capacity = 1;
while (capacity < 2 * numsSize) capacity <<= 1;
unsigned mask = (unsigned)(capacity - 1);
int* keys = malloc(capacity * sizeof *keys);
int* counts = calloc(capacity, sizeof *counts);
bool* used = calloc(capacity, sizeof *used);
for (int i = 0; i < numsSize; i++) {
unsigned slot = (unsigned)nums[i] * 2654435761u & mask;
while (used[slot] && keys[slot] != nums[i]) slot = (slot + 1) & mask;
if (!used[slot]) {
used[slot] = true;
keys[slot] = nums[i];
}
counts[slot]++;
}
int answer = 0; /* stays 0 only if the input breaks the rules */
for (int s = 0; s < capacity; s++) {
if (used[s] && counts[s] == 1) {
answer = keys[s];
break;
}
}
free(keys);
free(counts);
free(used);
return answer;
}
Fold every element into result with ^=. Since a ^ a is 0, a ^ 0 is a and the order does not matter, every pair cancels and the lone value is what remains. No allocation, no overflow, and the caller's array is only read.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
int singleNumber(int* nums, int numsSize) {
int result = 0;
for (int i = 0; i < numsSize; i++) {
result ^= nums[i]; /* pairs cancel: a ^ a == 0 */
}
return result;
}
Single Number in Kotlin
2 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
Count every value in a HashMap<Int, Int> with counts[n] = (counts[n] ?: 0) + 1: the Elvis operator turns a missing key into 0. Then destructure each entry as (value, count) and return the value whose count is 1. Linear time, with every distinct value boxed in the map.
class Solution {
fun singleNumber(nums: IntArray): Int {
val counts = HashMap<Int, Int>(nums.size)
for (n in nums) {
counts[n] = (counts[n] ?: 0) + 1
}
for ((value, count) in counts) {
if (count == 1) return value
}
return 0 // unreachable when the input follows the rules
}
}
Kotlin spells XOR as the infix function xor instead of an operator. nums.fold(0) { acc, n -> acc xor n } starts from 0 and folds every element in; each pair cancels because a xor a is 0, so the lone value is left. IntArray.fold is inlined, so it compiles to a plain loop over primitive ints.
class Solution {
fun singleNumber(nums: IntArray): Int =
nums.fold(0) { acc, n -> acc xor n } // pairs cancel
}
Single Number in Rust
2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
*counts.entry(n).or_insert(0) += 1 looks the key up once, inserts 0 when it is new and hands back a mutable reference to bump. A second loop over the map returns the value whose count is 1. The function still needs an i32 after that loop, so it ends with a fallback the rules never reach.
use std::collections::HashMap;
impl Solution {
pub fn single_number(nums: Vec<i32>) -> i32 {
let mut counts: HashMap<i32, u32> = HashMap::with_capacity(nums.len());
for &n in &nums {
*counts.entry(n).or_insert(0) += 1;
}
for (&value, &count) in &counts {
if count == 1 {
return value;
}
}
0 // unreachable when the input follows the rules
}
}
nums.iter().fold(0, |acc, &n| acc ^ n) XORs every element into an accumulator that starts at 0. Each pair cancels because a ^ a is 0, so the lone value is left. XOR never carries, so it cannot trip the overflow check that a debug build puts on +.
impl Solution {
pub fn single_number(nums: Vec<i32>) -> i32 {
nums.iter().fold(0, |acc, &n| acc ^ n) // pairs cancel
}
}
Single Number in Swift
2 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
counts[n, default: 0] += 1 reads a missing key as 0 and writes the incremented count back in one subscript. Then for (value, count) in counts where count == 1 returns the first value with a single copy. Swift requires an Int on every path, so a fallback follows the loop.
class Solution {
func singleNumber(_ nums: [Int]) -> Int {
var counts: [Int: Int] = [:]
counts.reserveCapacity(nums.count)
for n in nums {
counts[n, default: 0] += 1
}
for (value, count) in counts where count == 1 {
return value
}
return 0 // unreachable when the input follows the rules
}
}
Operators are functions in Swift, so nums.reduce(0, ^) passes the XOR operator itself as the combining closure. Starting from 0, every pair cancels because a ^ a is 0, and the lone value is the result. XOR never carries, so it cannot trap on overflow the way + can.
class Solution {
func singleNumber(_ nums: [Int]) -> Int {
nums.reduce(0, ^) // pairs cancel
}
}
Single Number in PHP
2 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
array_count_values runs in C and returns an associative array from each value to how often it appears. A foreach over it returns the key whose count is 1. Linear time, with an array entry for every distinct value.
<?php
class Solution {
/**
* @param int[] $nums
* @return int
*/
function singleNumber(array $nums): int {
$counts = array_count_values($nums); // value => copies
foreach ($counts as $value => $count) {
if ($count === 1) {
return $value;
}
}
return 0; // unreachable when the input follows the rules
}
}
Fold every element into $result with ^=. Because $a ^ $a is 0 and XOR ignores order, the pairs cancel and the lone value remains. PHP integers are 64-bit two's complement, so negative values cancel exactly like positive ones.
<?php
class Solution {
/**
* @param int[] $nums
* @return int
*/
function singleNumber(array $nums): int {
$result = 0;
foreach ($nums as $n) {
$result ^= $n; // pairs cancel
}
return $result;
}
}
Single Number in Ruby
2 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
Array#tally returns a Hash from each value to how often it appears, and Hash#key(1) returns the first key whose value is 1. Two built-in calls, both linear, with a hash entry for every distinct value.
# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)
nums.tally.key(1) # value => copies, then the key with one copy
end
nums.reduce(0, :^) sends ^ to an accumulator that starts at 0, once per element. Each pair cancels because a ^ a is 0, so the lone value is left. Ruby integers behave as if they had infinitely many sign bits, so negatives cancel too and nothing overflows.
# @param {Integer[]} nums
# @return {Integer}
def single_number(nums)
nums.reduce(0, :^) # pairs cancel
end
Single Number in Dart
2 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
counts.update(n, (c) => c + 1, ifAbsent: () => 1) bumps an existing count or inserts 1 in a single call. Then a loop over counts.entries returns the key whose value is 1. Linear time, with a map entry for every distinct value.
class Solution {
int singleNumber(List<int> nums) {
final counts = <int, int>{};
for (final n in nums) {
counts.update(n, (c) => c + 1, ifAbsent: () => 1);
}
for (final entry in counts.entries) {
if (entry.value == 1) return entry.key;
}
return 0; // unreachable when the input follows the rules
}
}
nums.fold(0, (acc, n) => acc ^ n) XORs every element into an accumulator that starts at 0. Every pair cancels because a ^ a is 0, and the lone value is the result. Dart int is 64-bit on the VM, so negative values cancel as two's complement.
class Solution {
int singleNumber(List<int> nums) {
return nums.fold(0, (acc, n) => acc ^ n); // pairs cancel
}
}
Single Number in Scala
2 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
Count with a mutable.HashMap[Int, Int]: counts(n) = counts.getOrElse(n, 0) + 1 reads a missing key as 0. Then collectFirst { case (value, 1) => value } pattern-matches the entry whose count is 1, so no return sits inside a closure. getOrElse(0) covers the case the rules never produce.
import scala.collection.mutable
object Solution {
def singleNumber(nums: Array[Int]): Int = {
val counts = mutable.HashMap.empty[Int, Int]
for (n <- nums) counts(n) = counts.getOrElse(n, 0) + 1
counts.collectFirst { case (value, 1) => value }.getOrElse(0)
}
}
nums.foldLeft(0)(_ ^ _) XORs every element into an accumulator that starts at 0. Each pair cancels because a ^ a is 0, so the lone value remains. JVM Int XOR is bitwise on two's complement, so negatives cancel too and nothing can overflow.
object Solution {
def singleNumber(nums: Array[Int]): Int =
nums.foldLeft(0)(_ ^ _) // pairs cancel
}
FAQ for Python
Can I write the XOR version in one line?
Yes: from functools import reduce and from operator import xor, then return reduce(xor, nums). Without an initial value reduce starts from the first element, which is fine here because the list is never empty; pass 0 as the third argument if it might be.
Why does XOR work with negative numbers in Python?
Python integers behave as if they had infinitely many sign bits, so -6 ^ -6 is 0 and -6 ^ 0 is -6, the same rules as for positives. The result never needs masking because nothing overflows.
Is there a set-based solution?
Toggle membership: add a value the first time you see it and remove it the second time, with seen ^= {n} or an explicit if n in seen: seen.remove(n) else: seen.add(n). At the end the set holds only the lone value, so return seen.pop(). It is O(n) time and up to O(n) space, like the counter.
What about 2 * sum(set(nums)) - sum(nums)?
It works: doubling the sum of the distinct values counts the lone value one time too many, and subtracting the real sum leaves exactly it. It still builds a set, so it uses O(n) space, and in languages with fixed-width integers the doubled sum can overflow. XOR has neither problem.
Why not nums.count(n) for each value?
list.count scans the whole list, so calling it for every element is O(n²): about 25 million comparisons on the largest case here, where a single pass needs 5,001 steps. Counting once with a dictionary or Counter is linear.
FAQ for JavaScript
Does the ^ operator work on any JavaScript number?
Only on 32-bit integers. Bitwise operators convert both operands to signed 32-bit integers first, so 2 ** 32 ^ 0 is 0 and 1.5 ^ 0 is 1. The values here stay within ±10⁹, which fits. For larger integers use BigInt values: nums.reduce((acc, n) => acc ^ n, 0n) with an array of BigInts.
Why pass 0 as the initial value to reduce?
Without it, reduce starts from the first element, which gives the same answer here, but on an empty array it throws a TypeError. With 0 an empty array returns 0 and the intent is clearer.
Why not use a plain object to count?
Object keys are strings, so counts[-5] is stored under the key '-5' and has to be converted back with Number before returning. A Map keeps the numbers as numbers and has no inherited keys.
Is a Set toggle shorter than counting?
A little: seen.has(n) ? seen.delete(n) : seen.add(n) inside the loop leaves only the lone value in the set, and return [...seen][0] reads it. It is still O(n) extra space; XOR is the only one of these that needs none.
Why not nums.filter with indexOf and lastIndexOf?
nums.find((n) => nums.indexOf(n) === nums.lastIndexOf(n)) reads nicely but scans the array twice for every element, which is O(n²): about 50 million steps on 5,001 numbers.
FAQ for TypeScript
Why does the reduce version need a typed initial value?
With nums.reduce((acc, n) => acc ^ n, 0) TypeScript infers number for the accumulator from the 0. Without the initial value it also infers number, but an empty array throws at runtime, which the types do not catch.
Can XOR overflow on large numbers?
It cannot overflow, but ^ truncates both sides to signed 32-bit integers, so values beyond ±2,147,483,647 come back wrong. The constraints stop at ±10⁹. For wider values switch the parameter to bigint[] and start from 0n.
Why ?? instead of || when reading the count?
counts.get(n) ?? 0 falls back only when the key is missing (undefined). With || the fallback also fires for a stored 0; that never happens when counting up from 1, but ?? says exactly what is meant.
Does the function need an explicit return type?
No, TypeScript infers number from both versions. Writing : number documents the contract and turns an accidental return undefined path into a compile error instead of a wrong answer.
FAQ for Java
Can the XOR version be written with streams?
Yes: return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);. IntStream keeps the values as primitives, so there is no boxing; a plain loop is still a little faster because it skips the lambda calls.
Why compare e.getValue() == 1 when the value is an Integer?
Comparing an Integer with the int literal 1 unboxes the Integer, so it is a numeric comparison and safe. The trap is == between two Integer objects, which compares references and fails outside the cached range of -128 to 127. Use equals or intValue() in that case.
Is a HashSet toggle better than counting?
It is shorter: if (!seen.add(n)) seen.remove(n); relies on add returning false for a value already present. At the end the set holds only the lone value, seen.iterator().next(). It is still O(n) space and boxes every value, like the map.
Can XOR overflow like a sum can?
No. XOR never carries from one bit into the next, so the result always fits in an int. A trick such as 2 * sum(distinct) - sum(all) can overflow on large values unless you do the math in long.
Would sorting the array work?
Yes: after Arrays.sort(nums) the pairs sit next to each other, so step through in twos and return the first nums[i] that differs from nums[i + 1], or the last element if none does. That is O(n log n) time, O(1) extra space, and it reorders the array you were given.
FAQ for Go
Is ^ in Go XOR or power?
XOR. Go has no power operator; 2 ^ 3 is 1, not 8. Used as a unary operator, ^x flips every bit of x, which is how Go spells bitwise NOT. Powers come from math.Pow on floats or a shift such as 1 << 3 for powers of two.
Does XOR work on negative ints in Go?
Yes. Signed integers are stored in two's complement and ^ works bit by bit, so -6 ^ -6 is 0 and -6 ^ 0 is -6. Nothing can overflow because XOR never carries between bits.
Can I use map[int]bool as a toggle instead of counting?
Yes: if seen[n] { delete(seen, n) } else { seen[n] = true } leaves exactly one key in the map, and for k := range seen { return k } returns it. It is the same O(n) space as counting; the XOR loop is the only allocation-free version.
Why give make a capacity hint?
make(map[int]int, len(nums)) reserves room for that many keys up front, so the map does not rehash while it fills. Only about half that many distinct keys arrive, so the hint over-allocates slightly; it is still cheaper than repeated growth.
FAQ for C#
Can LINQ do the XOR in one line?
Yes: return nums.Aggregate(0, (acc, n) => acc ^ n);. It runs the same fold through a delegate, so it is a bit slower than the foreach loop but has the same O(1) memory.
Is there a LINQ version of the counting approach?
nums.GroupBy(n => n).First(g => g.Count() == 1).Key reads well and is still linear, but it builds a group object and a list for every distinct value, so it allocates far more than the dictionary.
Why GetValueOrDefault instead of TryGetValue?
Both do one lookup for the read. GetValueOrDefault(n) returns 0 for a missing key, which is exactly the starting count, so the update fits in one line. CollectionsMarshal.GetValueRefOrAddDefault can cut the write lookup too, but it is rarely worth the extra ceremony.
Does XOR behave differently for negative ints in C#?
No. int is a 32-bit two's complement integer and ^ works bit by bit, so -6 ^ -6 is 0 like any other pair. Unlike +, XOR never carries between bits, so a checked context never throws for it.
Could a HashSet replace the dictionary?
Yes, as a toggle: if (!seen.Add(n)) seen.Remove(n); uses the fact that Add returns false for a value already present. The set ends with only the lone value, seen.First(). It is the same O(n) space.
FAQ for C++
Is there a standard algorithm for the XOR fold?
accumulate(nums.begin(), nums.end(), 0, bit_xor<int>()) from <numeric> and <functional> does it in one call. bit_xor<>() (the transparent form) works as well.
Why is counts[n]++ safe here when [] is a trap in other problems?
The [] operator inserts a default 0 for a missing key. When you only want to look a key up, that silently adds entries, so find is the right call. When you are counting, inserting a 0 and incrementing it is exactly what you want.
Is XOR on negative ints undefined behaviour?
No. Since C++20 signed integers are defined as two's complement, and ^ on them is well defined bit by bit. Signed overflow in + or * is still undefined, which is why a sum-based trick is riskier than XOR.
Would sorting the vector work?
Yes: after sort(nums.begin(), nums.end()) equal values sit next to each other, so check positions in steps of two and return the first nums[i] that differs from nums[i + 1], or the last element. That costs O(n log n) and modifies the vector the caller passed by reference.
Should I include bits/stdc++.h for accumulate?
No. It pulls in the whole standard library and adds a couple of seconds to every Run here. Include <numeric> for accumulate and <functional> for bit_xor.
FAQ for C
Is XOR on negative ints well defined in C?
Yes. Bitwise ^ on int is defined for every value, and since C23 signed integers are required to be two's complement (every mainstream compiler already was). -6 ^ -6 is 0, so negatives cancel like positives. Only arithmetic such as + or * can overflow, never ^.
Why does the hash table need a used array?
Every int, 0 included, can be a value in nums, so no key can stand for "empty". calloc gives a bool array that starts all false, which marks every slot free without reserving a value. The counts array comes from calloc too, so each new slot starts at 0.
Why multiply by 2654435761u before masking?
It is Knuth's multiplicative hash: the odd constant close to 2^32 divided by the golden ratio spreads nearby values across the table. Casting to unsigned first makes the multiplication wrap around legally, where a signed overflow would be undefined behaviour. With a power-of-two capacity, & mask replaces the slower %.
Would qsort work instead of a table?
Yes, in O(n log n): malloc a copy, memcpy the input into it and qsort it, then step through in twos and return the first copy[i] that differs from copy[i + 1], or the last element if none does. Compare with (x > y) - (x < y) in the comparator, never x - y, which overflows for values far apart.
Could the sum trick replace XOR?
2 * sum(distinct) - sum(all) gives the answer, but with values up to 10^9 the sums overflow an int after a handful of elements, and signed overflow is undefined behaviour. You would need long long and a set of distinct values anyway. XOR needs neither.
FAQ for Kotlin
Why does Kotlin not have a ^ operator?
Kotlin chose named infix functions for bitwise operations: xor, and, or, inv(), shl, shr and ushr. a xor b compiles to the same JVM instruction as Java's a ^ b, so there is no cost to the spelling.
Can I use groupingBy and eachCount?
nums.asList().groupingBy { it }.eachCount() builds the same Map<Int, Int> of counts, and .entries.first { it.value == 1 }.key picks the answer. groupingBy is not defined on IntArray directly, hence asList(), which wraps the array without copying it.
Is reduce better than fold here?
nums.reduce { acc, n -> acc xor n } starts from the first element instead of 0 and gives the same result, because the array is never empty. On an empty array reduce throws UnsupportedOperationException, while fold(0) returns 0, so fold is the safer habit.
Would a HashSet toggle use less memory?
A little: if (!seen.add(n)) seen.remove(n) keeps only values seen an odd number of times, and at the end seen.first() is the answer. It is still O(n) in the worst case and boxes each value, like the map. Only XOR runs in constant space.
Why return 0 after the loop in the HashMap version?
The compiler cannot know that some count is always 1, so a function with an Int return type needs a value on every path. return 0 satisfies it; error("no single value") is an alternative that fails loudly if the input breaks the rules.
FAQ for Rust
Is there a shorter way to write the fold?
Yes: nums.into_iter().reduce(|a, b| a ^ b).unwrap_or(0), or nums.iter().fold(0, std::ops::BitXor::bitxor) with the trait method as the closure. The plain fold with |acc, &n| acc ^ n is the most common and compiles to the same loop.
Why does the HashMap version need a 0 at the end?
Rust checks that every path returns an i32, and it cannot prove that some count equals 1. The trailing 0 satisfies the type checker; unreachable!() is the alternative that panics with a clear message if the input ever breaks the rules.
Could I find the answer with an iterator instead of the second loop?
counts.into_iter().find(|&(_, c)| c == 1).map(|(v, _)| v).unwrap_or(0) does the same in one expression. find stops at the first match, and unwrap_or replaces the fallback 0.
Why u32 for the counts and i32 for the keys?
A count is never negative, so u32 states that in the type; the keys are the input values, which can be negative, so they stay i32. The harness passes Vec<i32> and expects an i32 back, so no cast is needed for the answer.
Can XOR overflow in a debug build?
No. Debug builds panic on +, - and * overflow, but ^ works bit by bit and the result of two i32 values is always an i32. A sum-based trick such as 2 * distinct_sum - total would need i64 to stay safe here.
FAQ for Swift
Why can I pass ^ directly to reduce?
Swift operators are global functions, and ^ for Int has the type (Int, Int) -> Int, which is exactly what reduce expects as its second argument. nums.reduce(0) { $0 ^ $1 } is the same thing written as a closure.
What does the default: subscript do?
counts[n, default: 0] returns the stored value or 0 when the key is missing, and with += 1 it writes the result back in the same access. Without it you would write counts[n] = (counts[n] ?? 0) + 1, which hashes the key twice.
Is there a one-line dictionary version?
Dictionary(nums.map { ($0, 1) }, uniquingKeysWith: +) builds the counts, and .first { $0.value == 1 }?.key ?? 0 picks the answer. It allocates an extra array of pairs first, so the explicit loop is a little lighter.
Do I need import Foundation for any of this?
No. Dictionary, reduce and the ^ operator are all in the standard library. Importing Foundation adds about 1.5 s to every Run on this site and gives nothing here.
Would a Set toggle work?
Yes: if seen.remove(n) == nil { seen.insert(n) } keeps only values seen an odd number of times, and seen.first! is the answer at the end. It is O(n) time and up to O(n) space, like the dictionary; only XOR runs in constant space.
FAQ for PHP
Can I write the XOR version with array_reduce?
Yes: return array_reduce($nums, fn($acc, $n) => $acc ^ $n, 0);. It reads as one expression, but it calls the arrow function once per element, so the plain foreach is a little faster in PHP.
Why compare $count === 1 instead of == 1?
array_count_values returns integer counts, so === and == agree here. Strict comparison is the safer habit in PHP because == converts types first, for example "1" == 1 is true.
Does array_count_values work with negative numbers?
Yes. It accepts integers and strings, and any integer, negative or zero, is a valid array key, so -5 and 0 get their own counts. Floats or null in the array would trigger a warning and be skipped, which cannot happen with this input.
What is wrong with array_search(1, array_count_values($nums))?
Nothing: it returns the first key whose count is 1 and is a neat one-liner. Pass true as the third argument for a strict search, otherwise a loose comparison could match true or "1" in other contexts.
Can ^ ever give the wrong answer in PHP?
Only if the operands are not integers: ^ on two strings XORs their bytes and returns a string. The int[] parameter guarantees integers here, and declare(strict_types=1) would stop a string sneaking in elsewhere.
FAQ for Ruby
What does reduce(0, :^) actually do?
Passing a symbol makes reduce call that method on the accumulator with each element: ((0 ^ n1) ^ n2) ^ .... inject is an alias, and nums.reduce(:^) without the 0 starts from the first element, which also works because the array is never empty.
Which Ruby version has Array#tally?
tally arrived in Ruby 2.7. On older versions, nums.each_with_object(Hash.new(0)) { |n, h| h[n] += 1 } builds the same counts; Hash.new(0) makes missing keys read as 0.
Is Hash#key(1) slow?
Hash#key scans the entries in insertion order until a value equals 1, so it is O(n) in the worst case, the same order as building the tally. A hash lookup by value is never constant time; only lookups by key are.
Why not nums.find { |n| nums.count(n) == 1 }?
Array#count(n) scans the whole array, so calling it per element is O(n²): about 25 million comparisons on the largest case here. tally counts everything in one pass.
Can XOR misbehave with large or negative integers in Ruby?
No. Ruby Integer has arbitrary precision, and ^ treats negatives as two's complement with unlimited sign bits, so -6 ^ -6 is 0 and the result needs no masking.
FAQ for Dart
Is reduce or fold the right choice for XOR?
nums.reduce((a, b) => a ^ b) starts from the first element and works because the list is never empty; it throws a StateError on an empty list. fold(0, ...) returns 0 for an empty list and its type comes from the initial value, so it is the safer habit.
Why does Map.update need ifAbsent?
Without ifAbsent, update throws an ArgumentError when the key is missing. With it, a new key gets the value returned by ifAbsent and an existing one is passed through the update function, so one call handles both cases.
What order does the Map iterate in?
The {} literal creates a LinkedHashMap, which iterates in insertion order, so the loop sees values in the order they first appeared. Only one value has a count of 1, so the order does not change the answer.
Does XOR behave the same when Dart compiles to JavaScript?
Not quite: on the web, bitwise operators work on 32-bit values, so results outside that range differ from the VM. Inputs here fit in 32 bits, so ^ gives the same answer on both, but keep it in mind for larger numbers.
Would a Set toggle be simpler?
if (!seen.add(n)) seen.remove(n); relies on add returning false for a value already present, and seen.single is the answer at the end. It is O(n) time and up to O(n) space, like the map; only XOR runs in constant space.
FAQ for Scala
Is foldLeft on an Array[Int] slow because of boxing?
foldLeft on an array goes through a generic function, so the Int values are boxed on each call, but for 5,001 elements that costs microseconds. A while loop over indices with var acc = 0 avoids it entirely if you need the last bit of speed.
Can I use groupMapReduce instead of a mutable map?
Yes: nums.groupMapReduce(identity)(_ => 1)(_ + _) builds an immutable Map[Int, Int] of counts in one pass, and the same collectFirst { case (v, 1) => v } picks the answer. It is the purely functional version of the mutable loop.
Why collectFirst instead of returning from inside the loop?
A return inside the body of a for or foreach is a non-local return from a closure, which Scala 3 deprecates and warns about on every Run. collectFirst stops at the first match without one; boundary with break(value) is the other option.
What does case (value, 1) match?
Iterating a Map yields (key, value) tuples. The pattern case (value, 1) matches only tuples whose second element is the literal 1 and binds the first to value; collectFirst skips every tuple the partial function does not match.
Would reduce(_ ^ _) work too?
Yes, because the array is never empty: nums.reduce(_ ^ _) starts from the first element. On an empty array it throws UnsupportedOperationException, while foldLeft(0) returns 0.
Keep going
Counting Bits12 / 40 · Bit manipulation · EasyTry Single Number in Python (Single Number in Python), JavaScript (Single Number in JavaScript), TypeScript (Single Number in TypeScript), Java (Single Number in Java), Go (Single Number in Go), C++ (Single Number in C++), C (Single Number in C), Kotlin (Single Number in Kotlin), Rust (Single Number in Rust), Swift (Single Number in Swift), PHP (Single Number in PHP), Ruby (Single Number in Ruby), Dart (Single Number in Dart) or Scala (Single Number in Scala) instead.