XOR Coin Denomination (Story-Based)
E · easyP · Verified PYQbit-manipulation
Problem
A shopkeeper has coins of several denominations. Initially there are an even number of coins of each type. One coin is lost. Find the denomination of the lost coin. Input: First line = N (total coins remaining). Second line = N space-separated coin values.
Constraints
1 <= N <= 10\*\*5 (N is always odd after the loss)
Example
Input
7 1 1 2 2 3 3 4
Output
4
XOR all elements. All paired coins cancel to 0; only the odd-occurring denomination remains.
XOR of all values: 1^1^2^2^3^3^4 = 4. The lone coin is the lost denomination.