https://www.metacareers.com/profile/coding_practice_question/?problem_id=146466059993201&psid=275492097255885&practice_plan=0&p=GENERAL_SWE&b=0111022

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