## Sequence Equation

Sort 193 Discussions, By:

### Simple solution with explanation

From my HackerRank solutions.

Our input provides us n values of x and p(x)

p(x) is a one-to-one function, so it has an inverse. We create the function representing the inverse of p(x), and represent it as an array: int [] p_inverse

We need to find a y where p(p(y)) = x. This equation can be rewritten as
y = p_inverse(p_inverse(x)), which is the version of the equation we use to calculate and print y.

import java.util.Scanner;

public class Solution {
public static void main(String [] args) {
/* Create function: p_inverse */
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int [] p_inverse = new int[n + 1];
for (int x = 1; x <= n; x++) {
int px = scan.nextInt();
p_inverse[px] = x;
}
scan.close();

/* Calculate and print each y */
for (int x = 1; x <= n; x++) {
int y = p_inverse[p_inverse[x]];
System.out.println(y);
}
}
}


Let me know if you have any questions.

[deleted]

Much more easy n sexy java Code . . .

import java.util.*;
public class Solution {
public static void main(String args[] ){
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
HashMap<Integer,Integer> mp=new HashMap<Integer,Integer>();
for(int i=1;i<=n;i++)   mp.put(scan.nextInt(),i);
for(int i=1;i<=n;i++) System.out.println(mp.get(mp.get(i)));
}
}


Don't know why this solution has been downvoted that many times.

• MC

That's because the first code has complexity O(n) while the second code is having complexity O(n^2);

• SS
zurendra9 + 1 comment

The complexity of above second one is also O(n), as in first loop it takes input and in second it gives output. Both loops are isolated.

• MC
mehul_choksi98 + 1 comment

Didn't see that, my bad. Thanks for pointing that out.

• TB

I think the second will have complexity of nlogn because we have loop running for n times and inside loop we have get method of map which at best takes logn time(if we use binary search).

The time complexity to retrieve a value from a HashMap given a key is O(1).

• W

WOW

• golgoth + 1 comment

Maybe because "Self-praise is no recommendation."

And it is neither much more easy (fewer braces and indents) nor more sexy. Nothing that requires two nested for loops is sexy.

• CG

The for loops aren't nested though

The Complexity is nlogn not n2

• YO
ArrayList<Integer> list = new ArrayList<Integer>();
int n = in.nextInt();
for(int i = 0; i < n; i++)
for(int i = 1; i <= n; i++)
System.out.println(list.indexOf(list.indexOf(i)+1)+1);


I didn't understand the question until I read rshaghoulian's restatement of it. So thanks to you, rshaghoulian! Once I understood it was basically a numerical cryptogram I came up with this Ruby code:

length, sequence = gets.strip.to_i, gets.strip.split.map(&:to_i)

Decoder_ring = []
sequence.each_with_index do |x,i|
Decoder_ring[x-1] = i+1
end

def my_p_encode(n)
Decoder_ring[n - 1]
end

(1..length).each{|n| p my_p_encode(my_p_encode(n)) }

• sourav47 + 1 comment

will u explain this code with my test cases.. 10 5 4 6 7 8 9 9 10 5 4

• SK

Here in the problem statment given that each element in the sequence is distinct

Very Beautiful!

• AH

nice explain

• AK
kumaramijeet + 1 comment

I think there is an error in the given code.

p(x) can be anything in [1,50]

consider this as input:

5

20 21 1 5 6

the output should be : 4 3

but the above code will not produce any output.

• rshaghoulian + 1 comment
[deleted]
• AK
kumaramijeet + 1 comment

the first line contains an integer, 'n', denoting the number of elements in the sequence.

The second line contains 'n' space-separated integers denoting the respective values of p(1) , p(2) , ... p(n).

constraints:

1<=n<=50

1<=p(x)<=50 ; 1<= x <=n

suppose we input n=6, x will vary from 1 to n but p(x) can be anything from 1-50

The 1st 2 lines of the problem statement should answer your question.

"You are given a sequence of n integers, p(1), p(2),...,p(n). Each element in the sequence is distinct and satisfies 1 <= p(x) <= n". So your original input is actually invalid input.

Also, I spent some hackos downloading several sample inputs, and the input was always within 1 to n.

#include <iostream>

using namespace std;
int main() {
int n;
cin>>n;
int p[n+1];
for(int i=1;i<=n;i++){
int k;
cin>>k;
p[k]=i;
}
for(int i=1;i<=n;i++)cout<<p[p[i]]<<endl;
return 0;
}

• PM
Throghar + 1 comment

Very nice :) Different approach makes it much more easier.

Mine

using namespace std;
int main() {
int n;
cin  >> n;
vector<int> a(n);
for(int i=0;i<n;i++) {
cin >> a[i];
}
for(int i=1;i<=n;i++) {
cout << find(a.begin(),a.end(),find(a.begin(),a.end(),i) - a.begin() +1) - a.begin() +1 << endl;
}
return 0;

• manzar2525 + 1 comment

it's inversed equotation p(p(y)) = x... instead of maping the value on the index I map the index on given value... for exaplme the sample input0 p(p(y)) = 1 so I look which p index gave the value 1 which is index 3... now i know that p(y) = 3 so I look which index gave the value 3 which is index 2... and that's the y

It was a good approach!!

Wow, your approach doesn't require searching at all.

[deleted]
n = int(input().strip())
p = list(map(int,input().strip().split(' ')))
for i in range(n):
print(p.index(p.index(i+1)+1)+1)

''' Our task is :: For each x from 1 to n , print an integer denoting any valid y satisfying the equation p(p(y)) = x on a new line.
Here p(y) means, the value at y index in list p. But the range of y goes from 1 to n, and range of python list goes from 0 to n-1. so make it balanced, we need to add 1 in each time in y to make it equal to python index.

for example
3
2 3 1

Now, x goes from 1 to 3 (inclusive), but since the range goes from 0 to n-1, 1 needed to add here to balance it.

when i = 0, x = i+1, you need to find that at which index 1 is coming in list p
first_index = p.index(i+1)
now, u need to find at which index the first_index is coming, but since , the index coming as output in above line is from 0 to  n-1, 1 needed to add to balace it

second_index = p.index(first_index+1)

since this will also be 0 to n-1,, add 1

ans = second_index + 1

I have written a new code so u can understand how each line works
'''

n = int(input().strip())
p = list(map(int,input().strip().split(' ')))
for i in range(n):
x = i+1
first_index = p.index(x)
second_index = p.index(first_index + 1)
ans = second_index + 1
print(ans)


Nope, no hashmap is needed, and one can implement their own enumerate. Furthermore, the complexity can be O(n) instead of O(n^3) in index searching. :)

n = int(input()) + 1
prev = [0] * n
i = 0
for x in map(int, input().split()):
prev[x] = i = i + 1
print(*(prev[prev[i]] for i in range(1, n)), sep="\n")


thank u for nice code.. i am not good at knowing the complexity. but i am learning :)

• AA
alaniane + 1 comment

You are still using a hashmap. map is just a builtin hashmap.

• 1LovU + 1 comment

python map is something different. It applies the same function to all the iterables.

• AA
alaniane + 1 comment

In that case the best you can do is O(N*M) since map has to O(N) to iterate all of the elements. However, looking at the code what map is actually doing is creating a hashtable for you. It returns an array of the elements with the function applied to it. That is basically a hashtable.

Thanks for the info :)

• DG

Can u explain the code

impressive.

• WE

Mine was very similar

n = int(input())
numbers = [int(num) for num in input().split()]

for x in range(n):
print(numbers.index(numbers.index(x + 1) + 1) + 1)

• LeHarkunwar + 1 comment

Did it exactly this way, you're not the only one

I am Glad to hear that.

• A

Thanks for sharing! This is way simpler than my Python3 solution that nested loops

n = int(input().strip())
a = [int(temp_a) for temp_a in input().strip().split(' ')]

for x in range(1, n+1):
for num in range(len(a)):
if x == a[num]:
value = num + 1
for num in range(len(a)):
if value == a[num]:
print(num+1)


Same here :D

n = int(input().strip())
p = [int(a) for a in input().strip().split(' ')]
for i in range(1, n+1):
print(p.index(p.index(i)+1)+1)


Python 2.7+ without all the crap you don't need:

n = int( raw_input() )
a = list( map( int, raw_input().split() ) )
for i in range(n):
print( a.index( a.index(i + 1) + 1) + 1 )

• CS
cfshao_bjtu + 1 comment

You co seems very simple and nice. However, I don't understand it. Could you please explain to me how you approached the problem ? I cannot think out a way without using for loop. I am new to python.

Thank you very much cfshao

• CS

Hi Tyler, I just figured out how the list.index() works in Python. Never used it before. Thank you for sharing this usage and your solution with us.

I will conitue to find a solution without using a built-in function in case I am solving this problem in a job interview.

Unfortunately this is an O(N^2) solution, since a.index() is O(N).

• DG
Dimple151997 + 1 comment

can u explain the lAST LINE

• 1LovU + 1 comment
n = int(input().strip())
p = list(map(int,input().strip().split(' ')))
for i in range(n):
print(p.index(p.index(i+1)+1)+1)

''' Our task is :: For each x from 1 to n , print an integer denoting any valid y satisfying the equation p(p(y)) = x on a new line.
Here p(y) means, the value at y index in list p. But the range of y goes from 1 to n, and range of python list goes from 0 to n-1. so make it balanced, we need to add 1 in each time in y to make it equal to python index.

for example
3
2 3 1

Now, x goes from 1 to 3 (inclusive), but since the range goes from 0 to n-1, 1 needed to add here to balance it.

when i = 0, x = i+1, you need to find that at which index 1 is coming in list p
first_index = p.index(i+1)
now, u need to find at which index the first_index is coming, but since , the index coming as output in above line is from 0 to  n-1, 1 needed to add to balace it

second_index = p.index(first_index+1)

since this will also be 0 to n-1,, add 1

ans = second_index + 1

I have written a new code so u can understand how each line works
'''

n = int(input().strip())
p = list(map(int,input().strip().split(' ')))
for i in range(n):
x = i+1
first_index = p.index(x)
second_index = p.index(first_index + 1)
ans = second_index + 1
print(ans)

• VS
nvsr01 + 1 comment

Thank you for the explanation.

You are welcome :)

My Solutions

Checkout my Latest Solution - HackerRank Solutions

Solution in C# -

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Solution {
class Solution {
static void Main(string[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int[] arr = Array.ConvertAll(str, Int32.Parse);
for(int i=1;i<=t;i++)
{
int index1 = Array.IndexOf(arr, i)+1;
int index2 = Array.IndexOf(arr, index1)+1;
Console.WriteLine(index2);
}
}
}
}


Thank you, I hope this helps you to understand this problem clearly.

easy and simple solution

for(int x = 1; x <= n; x++){
for(int y = 1; y <= n; y++){
if(p[p[y]] == x)
printf("%d\n",y);
}
}

• R

Good solution

• MP

It is giving Runtive error for 4th test case .any suggestions?

[deleted]
• Spankajsingh + 1 comment

//This is the full solution. Got it.

#include <stdio.h>

int main() {
int n;
scanf("%d",&n);
int p[n+1];
for(int i = 1; i <= n; i++)
scanf("%d",&p[i]);
for(int x = 1; x <= n; x++){
for(int y = 1; y <= n; y++){
if(p[p[y]] == x)
printf("%d\n",y);
}
}

return 0;
}

• MP

Got it Thank you .

[deleted]
• FS
sir_fariz + 1 comment

does not it throw ArrayIndexOutOfBoundsException at p[n] ?

i am taking the size of array is n+1 not n.

what is the triple equals sign?

• RL

My easy C solution

int main() {
int n;
scanf("%d", &n);
int p;
int v[51];
for(int i = 1; i <= n; i++) {
scanf("%d", &p);
v[p] = i;
}
for(int i = 1; i <= n; i++) {
printf("%d\n", v[v[i]]);
}
return 0;
}

• RD
ramkumarmichael + 1 comment

can you explain me this solution... i didt understand the question

• RL

it's inversed equotation p(p(y)) = x... instead of maping the value on the index I map the index on given value... for exaplme the sample input0 p(p(y)) = 1 so I look which p index gave the value 1 which is index 3... now i know that p(y) = 3 so I look which index gave the value 3 which is index 2... and that's the y

great logic bro

this is Simplest Logic ............ good job

• MA

i can't understand explain the logic

• KD

C code

#include <stdio.h>
#include <stdlib.h>

int main() {
int n;
scanf("%d", &n);
int* a = (int*) malloc(sizeof(int)*n);
int* b = (int*) malloc(sizeof(int)*n);
for (int i = 0; i < n; i++) {
scanf("%d", a+i);
b[a[i]-1] = i+1;
}
for (int i = 0; i < n; i++) printf("%d\n", b[b[i]-1]);
return 0;
}

• koushik1998 + 1 comment

pls explain ur logic

• KD

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.

Using inverted p(x) in python:

n = int(raw_input())
p_temp = map(int, raw_input().split())
p = {v: k+1 for k, v in enumerate(p_temp)}
for i in range(1, n+1):
print p[p[i]]

static int[] permutationEquation(int[] p) {