This problem is from code forces. If you want to try this problem, follow this link.
Here is the simplified problem statement.
Given a group of N friends, each one has given a gift to other friend or themselves. An input array is given which indicates from whom each one has received their gifts. We have to print an array which shows to whom each one has given their gifts.
For example,
Let us consider a group of 5 friends. The input array {3, 1, 5, 2, 4} indicates that the ‘1’ has received the gift from ‘3’, and ‘2’ has received the gift from ‘1’, and so on…
The output should be {2, 4, 1, 5, 3}. This indicates that 1 has given gift to 2, 2 has given gift to 4, and so on…
This problem of finding the inverse permutation of a given sequence. The solution is described below.
Let us allocate a separate array B for output. For each A[i], fill B[A[i]] with i by iterating through all the elements. At the end of the iteration, B has the required answer. This method runs in O(n) time.
Here is the C++ implementation of the above approach.