Single Number

easyBit Manipulation+10 XPTime limit 2s

Every value in the array appears exactly twice, except one value that appears once. Find it.

Input:

line 1: n (odd)
line 2: n integers

Output: the value that appears once.

Constraints: 1 ≤ n ≤ 3·10⁴ + 1, −3·10⁴ ≤ value ≤ 3·10⁴.

Challenge: O(n) time and O(1) extra memory. Hint: x ^ x = 0 and x ^ 0 = x — XOR all the numbers together and the pairs cancel out.

Sample input 1

3
2 2 1

Sample output 1

Sample input 2

5
4 1 2 1 2

Sample output 2

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…