# Sequence Equation

# Sequence Equation

RodneyShag + 13 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 + 4 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

arun_pahilajani + 0 comments Loved it

abhayupadhyay + 1 comment complexity of retrieve any element from hashmap is o(1) but by this solution is downvoted so many time if someone have ans please tell me.

RodneyShag + 0 comments [deleted]

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 + 1 comment 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; }`

eduasinco + 0 comments Even easier:

`int[] q = new int[p.length]; for(int i: p){ q[p[p[i-1]-1]-1] = i; } return q;`

rahulrajpl + 1 comment 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)]

skvit001 + 0 comments @rahulrajpl How is the runtime complexity O(n)? p.index(i) will alone take O(n), but in your solution p.index(i) is inside another p.index() which makes the runtime complexity to be O(n2). Further, (p.index(p.index(i)+1)+1) ie., O(n2) statement executes max(p) or n times which makes the overall complexity O(n3)

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.

vishuatiet + 0 comments Nicely Done

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; }

Coder_AMiT + 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")

Coder_AMiT + 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.

Coder_AMiT + 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.

Coder_AMiT + 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

Coder_AMiT + 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

Coder_AMiT + 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)

nvsr01 + 1 comment Thank you for the explanation.

Coder_AMiT + 0 comments You are welcome :)

thigwyd + 0 comments what is the triple equals sign?

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.

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.

Sort 280 Discussions, By:

Please Login in order to post a comment