forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsingle_number.py
More file actions
39 lines (29 loc) · 887 Bytes
/
single_number.py
File metadata and controls
39 lines (29 loc) · 887 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
Single Number
Given an array of integers where every element appears twice except for
one, find the unique element using XOR.
Reference: https://en.wikipedia.org/wiki/Exclusive_or
Complexity:
Time: O(n)
Space: O(1)
"""
from __future__ import annotations
def single_number(nums: list[int]) -> int:
"""Find the element that appears only once (all others appear twice).
XORs all values together; paired values cancel to zero, leaving the
unique value.
Args:
nums: A list of integers where every element except one appears
an even number of times.
Returns:
The single element, or 0 if all elements are paired.
Examples:
>>> single_number([1, 0, 2, 1, 2, 3, 3])
0
>>> single_number([101])
101
"""
result = 0
for number in nums:
result ^= number
return result