Single Number
Easy About 8 min Free, no account needed
One value appears an odd number of times - XOR finds it for free.
The brief
In nums, every value appears an even number of times except one value,
which appears an odd number of times. Return that value.
The obvious approach counts every element's occurrences, O(n2) on the hidden 200,000-element test, so it's too slow. You will need a single linear pass, and ideally no extra memory.
Starter code
using System;
public class Solution
{
// TODO: return the value appearing an odd number of times.
public int SingleNumber(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Bit manipulation
- Use masks, shifts and XOR on the binary representation directly.
Related katas
- Counting Bits Easy Free Popcounts for 0..n - reuse the table you are already building.
- Power of Two Easy Free One bit trick, two edge cases waiting to bite.
- Reverse Bits Easy Free Reverse a 32-bit pattern - signed shifts will betray you.
- Gray Code at an Index Medium Free The n-th Gray code without generating the first n-1.