# Sequence Equation

# Sequence Equation

RodneyShag + 12 comments ### 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_inverseWe 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.

Neelaesh + 0 comments [deleted]rudra_utpal + 2 comments 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))); } }

japkeerat21 + 3 comments Don't know why this solution has been downvoted that many times.

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

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.

mehul_choksi98 + 1 comment Didn't see that, my bad. Thanks for pointing that out.

tarabahadur_tha1 + 1 comment 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).

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

widefin + 0 comments 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.

crisagazzola + 0 comments The for loops aren't nested though

kishynivas10 + 0 comments It was downvoted, because it didn't use the property of the given array.

rudra_utpal + 0 comments The Complexity is nlogn not n2

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

JDenman6 + 0 comments 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

sivanikankipati + 0 comments Here in the problem statment given that each element in the sequence is distinct

BelieveInMagic + 0 comments **Very Beautiful!**ashokharijan97 + 0 comments nice explain

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.

RodneyShag + 1 comment [deleted]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

RodneyShag + 0 comments 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.

kalra_bonisha + 0 comments Below is a much easier solution:

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

`int[] resultArr = new int[p.length]; for(int i=0; i<p.length; i++) { resultArr[p[p[p[i]-1]-1]-1] = p[i]; } return resultArr; }`

rahulrajpl + 0 comments For Python lovers ...in O(n) time

def permutationEquation(p): return [(p.index(p.index(i)+1)+1) for i in range(1, max(p)+1)]

satyakibose98 + 0 comments Still the problem is not clear to me.

manojshukla1466 + 0 comments really impressive solution, I was doing it in O(n). thanks for the wonderful logic.

pavankalyan_93 + 7 comments #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; }

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 + 0 comments [deleted]

manzar2525 + 1 comment Can you please explain your logic

Cypher713_net + 0 comments 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

manzar2525 + 0 comments Can you please explain your logic.

akanksha_kumari + 0 comments It was a good approach!!

rufus17 + 0 comments Wow, your approach doesn't require searching at all.

Cypher713_net + 0 comments [deleted]kg1020 + 0 comments Why this is not working? Any guess?

// Complete the permutationEquation function below. vector<int> permutationEquation(vector<int> p) { vector<int> q(p.size()); for(const auto& i:p){ q[i-1] = p[p[i-1]-1]; } return q; }

1LovU + 8 comments 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)

delamath + 3 comments 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")

1LovU + 0 comments thank u for nice code.. i am not good at knowing the complexity. but i am learning :)

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.

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.

1LovU + 0 comments Thanks for the info :)

Dimple151997 + 0 comments Can u explain the code

Freak_1231 + 0 comments impressive.

Aximm + 0 comments 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

1LovU + 0 comments I am Glad to hear that.

alison_thaung + 0 comments 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)

shtolcers + 0 comments 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)

tyler_christian2 + 2 comments 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 )

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

cfshao_bjtu + 0 comments 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.

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

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)

thigwyd + 0 comments what is the triple equals sign?

Rys23 + 4 comments 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; }

ramkumarmichael + 1 comment can you explain me this solution... i didt understand the question

Rys23 + 0 comments 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

koushik1998 + 0 comments great logic bro

singh_surajkumar + 0 comments this is Simplest Logic ............ good job

ggmurali6 + 0 comments i can't understand explain the logic

daskunal + 1 comment 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

daskunal + 0 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.

kovab93 + 0 comments 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]]

sagarmalik + 1 comment following the pre generated boiler plate code structure

static int[] permutationEquation(int[] p) { int []sol=new int[p.length]; for(int i:p) sol[p[p[i-1]-1]-1]=i; return sol; }

yinqiankong + 0 comments this is exactly what I expected

multipletricks_1 + 0 comments **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 t = Convert.ToInt32(Console.ReadLine()); string[] str = Console.ReadLine().Split(' '); 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.

Spankajsingh + 2 comments 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); } }

rejwancse10 + 2 comments Good solution

madhu703 + 2 comments It is giving Runtive error for 4th test case .any suggestions?

Spankajsingh + 0 comments [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; }

madhu703 + 0 comments Got it Thank you .

Spankajsingh + 0 comments [deleted]

sir_fariz + 1 comment does not it throw ArrayIndexOutOfBoundsException at p[n] ?

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

Sort 249 Discussions, By:

Please Login in order to post a comment