Your browser is not supported. Please, update your browser or switch to a different one. Learn more about what browsers are supported.

Check out Codility training tasks
Tasks Details
easy
Find value that occurs in odd number of elements.
Task Score
88%
Correctness
100%
Performance
75%

Task description

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9
  • the elements at indexes 0 and 2 have value 9,
  • the elements at indexes 1 and 3 have value 3,
  • the elements at indexes 4 and 6 have value 9,
  • the element at index 5 has value 7 and is unpaired.

Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

  • N is an odd integer within the range [1..1,000,000];
  • each element of array A is an integer within the range [1..1,000,000,000];
  • all but one of the values in A occur an even number of times.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 32 minutes
Notes
not defined yet
Task timeline
11:47:54
12:19:32

Away from Codility tab

0%

Code: 12:19:32 UTC, cpp, final, score:  88
// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std;

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    map<int, int> m1;
    map<int, int>::iterator iter;

    for(int i=0; i<A.size(); i++){
        //map에 없으면 map에 넣기
        if(m1.find(A[i]) == m1.end()){
            m1.insert({A[i], 1});
        }else{
            m1[A[i]] += 1;
        }
    }

    for(iter=m1.begin(); iter!=m1.end(); iter++){
        if(iter->second %2 == 1){
            return iter->first;
        }
    }
}
Analysis summary

The following issues have been detected: timeout errors.

Analysis
Detected time complexity:
O(N) or O(N*log(N))
expand all Example tests
example1
example test
OK
expand all Correctness tests
simple1
simple test n=5
OK
simple2
simple test n=11
OK
extreme_single_item
[42]
OK
small1
small random test n=201
OK
small2
small random test n=601
OK
expand all Performance tests
medium1
medium random test n=2,001
OK
medium2
medium random test n=100,003
OK
big1
big random test n=999,999, multiple repetitions
OK
big2
big random test n=999,999
TIMEOUT ERROR
running time: 0.652 sec., time limit: 0.352 sec.