Passing Yearbooks

Straight to the Point !

Are you landed to this page and rushing for the immediate solution in javascript. here you go !!

Step 1: Create new array with same value from given array length.
Step 2: Iterate given book array.

1function findSignatureCounts(arr) {
2  // Write your code here
3  const result = Array(arr.length).fill(1);
4  for(let i=0; i<arr.length; i++) {
5    let holding = arr[i] - 1;
6    const myself = i;
7    while(holding !== myself) {
8      holding = arr[holding] - 1;
9      result[i]++;
10    }
11  }
12  return result;
13}

On High level note, It worth to read in detail for a better understanding.

Problem Statement
Solutions
Other Possible Questions

Problem Statement

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.

1int[] findSignatureCounts(int[] arr)

Constraints

n is in the range [1, 100,000].
Each value arr[i] is in the range [1, n], and all values in arr[i] are distinct.

Expected

Return a list of n integers output, as described above.

Test Cases

n = 2, arr = [2, 1] and output = [2, 2]
n = 2, arr = [1, 2] and output = [1, 1]

Foot Note

Test Case 1 Explaination:
- Pass 1:
  - Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is Student 2.
  - Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is Student 1.
- Pass 2:
  - Student 1 signs Student 2's yearbook. Then they pass it to the student at arr[0], which is Student 2.
  - Student 2 signs Student 1's yearbook. Then they pass it to the student at arr[1], which is Student 1.
- Pass 3:
  - Both students now hold their own yearbook, so the process is complete.
- Result: Each student received 2 signatures.
Test Case 2 Explaination:
- Pass 1:
  - Student 1 signs their own yearbook. Then they pass the book to the student at arr[0], which is themself, Student 1.
  - Student 2 signs their own yearbook. Then they pass the book to the student at arr[1], which is themself, Student 2.
- Pass 2:
  - Both students now hold their own yearbook, so the process is complete.
- Result: Each student received 1 signature.