Loading...

Sort 193 Discussions, By:

  • rshaghoulian + 8 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_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.

    • 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 + 2 comments

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

        • MC
          mehul_choksi98 + 2 comments

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

          • W
            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.

          • CG
            crisagazzola + 0 comments

            The for loops aren't nested though

      • rudra_utpal + 0 comments

        The Complexity is nlogn not n2

    • YO
      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

      • SK
        sivanikankipati + 0 comments

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

    • BelieveInMagic + 0 comments

      Very Beautiful!

    • AH
      ashokharijan97 + 0 comments

      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

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

            HackerRank solutions.

  • pavankalyan_93 + 6 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;
    }
    
    • 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

      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]
  • 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 :)

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

            • 1LovU + 0 comments

              Thanks for the info :)

      • DG
        Dimple151997 + 0 comments

        Can u explain the code

    • Freak_1231 + 0 comments

      impressive.

    • WE
      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.

    • A
      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 )
      
      • CS
        cfshao_bjtu + 1 comment

        Hi @tyler_christian

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

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

          • 1LovU + 0 comments

            You are welcome :)

  • 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);
            }
        }
    
    • R
      rejwancse10 + 2 comments

      Good solution

      • MP
        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;
          }
          
          • MP
            madhu703 + 0 comments

            Got it Thank you .

      • Spankajsingh + 0 comments
        [deleted]
    • FS
      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.

  • thigwyd + 0 comments

    what is the triple equals sign?

  • RL
    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;
    }
    
    • RD
      ramkumarmichael + 1 comment

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

      • RL
        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

    • MA
      ggmurali6 + 0 comments

      i can't understand explain the logic

  • KD
    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

      • KD
        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 + 0 comments

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