[Codility] Lesson-02.2: OddOccurrencesInArray

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.

  • 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.
  • 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.

Key Point

  • It can be solved simply by using the ‘Exclusive OR (XOR)’ operation. Because the XOR operation neutralizes elements that are paired with each other (In the XOR operation, the output of the paired inputs is 0).

Solution (using Python)

Refer that, XOR operator is ‘^’ in python and some other programming languages.

def solution(A):
ans = 0
for elm in A: ans = ans ^ elm
return ans

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store