3
\$\begingroup\$

Question:

There are n students, numbered from 1 to n, each with their own yearbook. They would like to pass their yearbooks around and get them signed by other students.

You're given a list of n integers arr[1..n], which is guaranteed to be a permutation of 1..n (in other words, it includes the integers from 1 to n exactly once each, in some order). The meaning of this list is described below.

Initially, each student is holding their own yearbook. The students will then repeat the following two steps each minute: Each student i will first sign the yearbook that they're currently holding (which may either belong to themselves or to another student), and then they'll pass it to student arr[i-1]. It's possible that arr[i-1] = i for any given i, in which case student i will pass their yearbook back to themselves. Once a student has received their own yearbook back, they will hold on to it and no longer participate in the passing process. It's guaranteed that, for any possible valid input, each student will eventually receive their own yearbook back and will never end up holding more than one yearbook at a time.

You must compute a list of n integers output, whose element at i-1 is equal to the number of signatures that will be present in student i's yearbook once they receive it back.

Solution: I have come up with a C# solution. I am not sure whether this is \$O(n)\$. I think it comes to \$O(arraySize * noOfCyclesPossible)\$, so if \$noOfCyclesPossible\$ leads to \$arraySize\$ then its \$O(n^2)\$.

Also would be nice if someone can tell me whether the solution can be optimized without copy of the working array.

private static int[] findSignatureCounts(int[] arr) {

    bool[] locked = new bool[arr.Length];    
    int[] signaturesCount = new int[arr.Length];
    
    int[] yearBookPositionsEndOfCycle = new int[arr.Length];
    int[] yearBookPositionsWorkingCycle = new int[arr.Length];
    
    Array.Copy(arr, yearBookPositionsWorkingCycle, arr.Length);
    
    int j = 0;
    while(j < arr.Length - 2){
      
      j = 0;
      
      Array.Copy(yearBookPositionsWorkingCycle, yearBookPositionsEndOfCycle, arr.Length);
    
      for(int i = 0; i < arr.Length; i++){
        
        int studentId = arr[i];
              
        if(locked[studentId - 1]) continue; 
        
        yearBookPositionsWorkingCycle[studentId - 1] = yearBookPositionsEndOfCycle[i]; 
        
        if(yearBookPositionsWorkingCycle[studentId - 1] == arr[studentId - 1])  locked[studentId - 1] = true;
    
        if(locked[studentId - 1]) j++; 
        
        signaturesCount[i] += 1;
      }
    }
    
    for(int i = 0; i < arr.Length; i++){
        Console.WriteLine(signaturesCount[i]);
    }
    
    // Write your code here
    return signaturesCount;
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Question:

I would suggest to ignore the "fluff" of the pretend real-world example and try to translate the problem into its general terms. I believe, with a small twist, that this question is equivalent to this one (the link contains "spoilers" if that kind of thing is relevant to you) https://math.stackexchange.com/questions/4157503/algorithm-for-finding-the-cycle-decomposition-of-a-permutation

I am not sure whether this is O(n).

Also would be nice if someone can tell me whether the solution can be optimized without copy of the working array.

Your version might not be O(n) [I have not checked in detail, but it seems uneccessarily complicated] but by extension of the discussion in the link I provided there must be a linear algorithm that touches each element at most 3 times:

  • to determine the length of the cycle starting at that element
  • to propagate the cycle-length to all the elements on the cycle [this is a quirk of how the problem is stated]
  • to check if the element has already been processed as part of another cycle

I am not sure about the etiquette in these parts, I suppose formulating that algorithm should be left as an exercise to the reader?

The implementation will likely have two nested loops so naively it might look like O(n^2) similar to your own analysis but I think the argument that each element is touched a constant number of times is compelling. In particular every element already touched by the inner loop should be skipped by the outer loop. Your algorithm does not seem to have this property, your outer loop neither skips nor does it mark elements for skipping.

Solution:

Basic code review stuff, irrespective of the algorithm:

findSignatureCounts vs. signaturesCount ??? The plural switches from Count to Signature

arr and locked are not great names.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.