OddOccurrencesInArray at app.codility.com-programmers in C Plus Plus Explained - Find value that occurs in odd number of elements.
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 21 Jan 2024
Task
Detected time complexity : O(N) or O(N*log(N))
Lesson 2 at app.codility.com/programmers
The solution and its explanation are given below.
Problem
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.
Note
The above list has been arranged as follows:
Element: 9 3 9 3 9 7 9
Index: 0 1 2 3 4 5 6
The paired elements are 9 and 3. This can be deceiving. An algorithm code written, based on this setup, would not work for other setups, for the same criteria and conditions of the task (problem). The paired elements could have been 9, 3, and 8; as in the following arrangement:
Element: 9 3 9 3 8 7 8
Index: 0 1 2 3 4 5 6
This can still be deceiving because, for each pair, the second element occurs after one element. That is: for the pair of 9, the second 9 occurs after 3; for the pair of 3, the second 3 occurs after 9; for the pair of 8, the second pair occurs after 7. An algorithm code written, based on this arrangement, would not work for other arrangements, for the same criteria and conditions, of the task (problem). The arrangement could otherwise have been:
Element: 9 9 3 3 8 8 7
Index: 0 1 2 3 4 5 6
There are still other deceiving arrangements.
Efficient Algorithm
The last three line conditions in the given problem above, are not really to be verified, by the code of the student (candidate). It should be assumed that they are implied in the given data.
It can be unnecessarily difficult to write the function in a brute force way. A fast (efficient) algorithm is to sort the vector (array), and then find the element that does not have a pair, in a final one scan of the vector. That element would be in an odd number position. The program is (read the code and comments):
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
if (N == 1)
return A[0];
else {
sort(A.begin(), A.end());
for (int i=0; i<N-2; i+=2) {
if (A[i] != A[i+1])
return A[i]; //0 is odd for zero based indexing
}
}
return A[N-1];
}
int main()
{
vector<int> B{9, 3, 9, 3, 9, 7, 9};
int odd = solution(B);
cout << odd << endl;
return 0;
}
Remember, at codility.com/programmers, the C++ main function is not typed (sent). The solution code begins with the determination of the number of elements in the vector. There after, if the vector contains only one element, then the one element is not paired, and it is returned.
Otherwise, the list is sorted, and scanned from the beginning. After sorting, as the list is scanned, paired elements occur next to one another. And so there has to be a for-loop that increments by 2 and not 1. The unpaired element will be found in an odd position.
For the given vector,
vector<int> B{9, 3, 9, 3, 9, 7, 9};
after sorting, the vector is:
vector<int> B{3, 3, 7, 9, 9, 9, 9};
The element that is not paired is 7, and it is in the third position, which is zero-based index 2 (ordinal position \96 1 = zero based index). With zero-based indexing, 0 is in an odd position, which is the first ordinal position; and one is in an even position. The reader should not confuse between zero-based index positioning and normal cardinal positioning of: 1, 2, 3, 4, 5. etc. With normal cardinal positioning, 2 is in an even position, while with zero-based index positioning, 2 is in an odd position (actually third ordinal position).
Note that the while-condition in the for-loop is (i<N-2).
If the unpaired value is at the end of the list, it is still returned, because in the body of the for-loop, A[i] is compared with A[i+1] , and zero-based indexing ends at N-1.
The reader should register at app.codility.com/programmers to be testing his/her own code.
That is it, for the explanation of the task.