cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2009 · MediumBitwise Xor

Odd Multiplicity

National Olympiad — National round

Submission name: odd.cpp

Solve in Editor →

Problem summary

Exactly one value occurs an odd number of times in the given sequence; every other value occurs an even number of times. Find it.

Input

Odd N, followed by N positive integers.

Output

The value of odd multiplicity.

Constraints

2 < N < 1,000,000; values 1…10¹³.

Worked example

An independently prepared example for this explanation.

Input

5 8 2 8 2 8

Output

8

Solution analysis

  1. XOR all values into a 64-bit accumulator.

Why it works

Equal values cancel in pairs because x XOR x=0. The single unpaired value remains.

Complexity: O(N) time, O(1) space.

Watch out. 32-bit integers cannot hold the allowed values.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Equal values cancel in pairs because x XOR x=0. The single unpaired value remains.
#include<iostream>
#include<tuple>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    long long ans=0,x;
    while(n--){
        cin>>x;
        ans^=x;
    }
    cout<<ans<<'\n';
}

Source: Arena Olimpiici ↗