## Sequence Equation

rshaghoulian ### 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 [deleted]rudra_utpal 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 Don't know why this solution has been downvoted that many times.

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

zurendra9 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 Didn't see that, my bad. Thanks for pointing that out.

tarabahadur_tha1 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 The time complexity to retrieve a value from a HashMap given a key is O(1).

widefin WOW

golgoth 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 The for loops aren't nested though

rudra_utpal The Complexity is nlogn not n2

VictoryNicholas 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 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 will u explain this code with my test cases.. 10 5 4 6 7 8 9 9 10 5 4

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

BelieveInMagic **Very Beautiful!**ashokharijan97 nice explain

kumaramijeet 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 [deleted]kumaramijeet 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

rshaghoulian 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.

pavankalyan_93 #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 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 [deleted]

manzar2525 Can you please explain your logic

Cypher713_net 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 Can you please explain your logic.

akanksha_kumari It was a good approach!!

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

Cypher713_net [deleted]

1LovU 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 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 thank u for nice code.. i am not good at knowing the complexity. but i am learning :)

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

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

alaniane 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 Thanks for the info :)

Dimple151997 Can u explain the code

Freak_1231 impressive.

Aximm 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 Did it exactly this way, you're not the only one

1LovU I am Glad to hear that.

alison_thaung 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 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 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 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 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 Unfortunately this is an O(N^2) solution, since a.index() is O(N).

Dimple151997 can u explain the lAST LINE

1LovU 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)

multipletricks_1 **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 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 Good solution

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

Spankajsingh [deleted]Spankajsingh //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 Got it Thank you .

Spankajsingh [deleted]

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

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

thigwyd what is the triple equals sign?

Rys23 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 can you explain me this solution... i didt understand the question

Rys23 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 great logic bro

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

ggmurali6 i can't understand explain the logic

daskunal 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 pls explain ur logic

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

Sort 193 Discussions, By:

Please Login in order to post a comment