PermMissingElem at app.codility.com-programmers in C Plus Plus Explained - Find the missing element in a given permutation
Foreword: Category of Article - Technology, Computers and Software, Algorithm
By: Chrysanthus Date Published: 21 Jan 2024
Task
Detected time complexity : O(Nxlog(N))
Lesson 3 at app.codility.com/programmers
The solution and its explanation are given below.
Problem
An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
int solution(vector<int> &A);
that, given an array A, returns the value of the missing element.
For example, given array A such that:
A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.
Write an efficient algorithm for the following assumptions:
\95 N is an integer within the range [0..100,000];
\95 the elements of A are all distinct;
\95 each element of array A is an integer within the range [1..(N + 1)].
Note:
The values in the array start from 1 to N + 1. They are simply not arranged in ascending order. In the illustration array, of the problem, there are 4 elements, and when arranged in ascending order, they become 1, 2, 3, 5. It can clearly be seen from this ascending order, that 4 is missing.
It can be very cumbersome to do this the brute-force (direct) way. The best way to do it is to sort the array (vector), and then scan it for the missing element. This will give O(Nxlog(N)) time complexity at app.codility.com/programmers
Solution
app.codility.com/programmers allows the candidate to use the predefined sort() function in C++. It is in the algorithm library, which has to be included. The following program offers the solution (read the code and comments):
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//sort using C++ sort, then look for the missing element from the beginning
int solution(vector<int> &A) {
int N = A.size();
sort(A.begin(), A.end()); //sort function from the algorithm library
int ctr = 1; //counter
for (int i=0; i<N; i++){
if (ctr != A[i])
return ctr; //missing element
++ctr;
}
return ctr; //element is missed at end of list
}
int main()
{
vector<int> B{2, 3, 1, 5};
int miss = solution(B);
cout << miss << endl;
return 0;
}
The value of ctr is incremented at the end of the for-loop\92s body. It is synchronized with the sorted elements. In the for-loop scan, when it is not equal to a sorted element, then its value is the missing element; otherwise the element is missed at the end of list.
The example test has been used here. On submission at app.codility.com/programmers, at least 8 test cases not shown here will assess your solution. Remember that at app.codility.com/programmers, the C++ main() function is not submitted.
Conclusion
To solve a similar problem, efficiently, sort the array or vector, and then scan for the missing element.
The reader should register at app.codility.com/programmers and be testing his/her code, to gain confidence.