bit-manipulation · Problem 1 of 1
Single Number
Every value in nums appears exactly twice, except one that appears once.
Return that one.
singleNumber([4, 1, 2, 1, 2]) -> 4
A set or a counter solves it in O(n) time and O(n) space. There is a way to do it in O(1) space, and it is the reason this problem is a bit-manipulation problem rather than a hashing one.
Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| singleNumber([2,2,1]) | the odd one out is last | 1 | — |
| singleNumber([4,1,2,1,2]) | unpaired value in the middle | 4 | — |
| singleNumber([7]) | a single element is its own answer | 7 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(1)
One pass and a single accumulator. The hash-set solution is the same time but O(n) space — this is the rare case where the clever answer is also the simpler one to write.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left