We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You are given a sequence of integers, p(1), p(2), ..., p(n)
That means, the array name is p, and length is n.
Each element in the sequence is distinct and satisfies 1 <= p(x) <= n.
That means, all the numbers between 1 and n inclusive, are members of p array, in random order.
Suppose x is a number between 1 and n.
For each x where 1 <= x <= n, we have to find any integer y such that p(p(y)) = x.
What does that mean?
Suppose the array p is [3, 1, 5, 2, 4]
For x = 1, we have to find a y so that p(p(y)) = 1.
We can see here that p(2) = 1
Therefore p(y) = 2
We can see, p(4) = 2. Therefore y = 4.
Similarly, for x = 2, we get p(4) = 2.
That is, p(y) = 4
So y = 5.
How to do that in program?
One way is that, we take another array q of same length
q(z) = p(p(y)) = x
Take example of the above array.
q array has five indices 1, 2, 3, 4, 5.
In another way, we can tell, q array has five indices p(1), p(2), p(3), p(4), and p(5), as {1,2,3,4,5} = {p(1), p(2), p(3), p(4), p(5)}
If we write indices of an array along with value, and write them in any order, p array will be [1:3, 2:1, 3:5, 4:2, 5:4]
Here we have written it in index:value format
q array will be [p(1):1, p(2):2, p(3):3, p(4):4, p(5):5]
So, here, q = [3:1, 1:2 , 5:3 , 2:4 , 4:5]
If we write q array is sorted form, q = [2, 4, 1, 5, 3]
So, for every x index in p, p(p(y)) = x => q(x) = y.
In the actual program, +1 or -1 adjust ment in the line b[a[i]-1] = i+1; was required to adjust between 1-base concept and 0-base implementation of array.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sequence Equation
You are viewing a single comment's thread. Return to all comments →
You are given a sequence of integers, p(1), p(2), ..., p(n) That means, the array name is p, and length is n.
Each element in the sequence is distinct and satisfies 1 <= p(x) <= n. That means, all the numbers between 1 and n inclusive, are members of p array, in random order.
Suppose x is a number between 1 and n. For each x where 1 <= x <= n, we have to find any integer y such that p(p(y)) = x.
What does that mean? Suppose the array p is [3, 1, 5, 2, 4] For x = 1, we have to find a y so that p(p(y)) = 1. We can see here that p(2) = 1 Therefore p(y) = 2 We can see, p(4) = 2. Therefore y = 4.
Similarly, for x = 2, we get p(4) = 2. That is, p(y) = 4 So y = 5.
How to do that in program? One way is that, we take another array q of same length q(z) = p(p(y)) = x
Take example of the above array. q array has five indices 1, 2, 3, 4, 5. In another way, we can tell, q array has five indices p(1), p(2), p(3), p(4), and p(5), as {1,2,3,4,5} = {p(1), p(2), p(3), p(4), p(5)}
If we write indices of an array along with value, and write them in any order, p array will be [1:3, 2:1, 3:5, 4:2, 5:4] Here we have written it in index:value format
q array will be [p(1):1, p(2):2, p(3):3, p(4):4, p(5):5]
So, here, q = [3:1, 1:2 , 5:3 , 2:4 , 4:5] If we write q array is sorted form, q = [2, 4, 1, 5, 3]
So, for every x index in p, p(p(y)) = x => q(x) = y.
In the actual program, +1 or -1 adjust ment in the line b[a[i]-1] = i+1; was required to adjust between 1-base concept and 0-base implementation of array.