Количество проходов, необходимых для повторного посещения того же индекса путем перемещения arr[i] в индекс arr[i]

Учитывая массив (индексация на основе 1) arr[] перестановки первых N натуральных чисел, задача для каждого элемента состоит в том, чтобы найти количество ходов, необходимых для достижения этого индекса, так что при каждом перемещении элемент массива с индексом i перемещается в элемент массива с индексом arr[i] .

Примеры:

Input: arr[] = {2, 3, 1}
Output: 3 3 3  
Explanation:
For array element arr[1] = 2, the set of moves of indices are 1 -> 2 -> 3 -> 1. The total count of moves required is 3.
For array element arr[2] = 3, the set of moves of indices are 2 -> 3 -> 1 -> 2. The total count of moves required is 3.
For array element arr[3] = 1, the set of moves of indices are 3 -> 1 -> 2 -> 3. The total count of moves required is 3.

Input: arr[] = {4, 6, 2, 1, 5, 3}
Output: 2 3 3 2 1 3

Подход: Данную проблему можно решить, найдя количество ходов, необходимых для каждого элемента массива для каждого индекса. Выполните следующие шаги, чтобы решить данную проблему:

• Пройдите по заданному массиву arr[] с помощью переменной i и выполните следующие шаги:
  • Инициализируйте переменную, скажем, count , которая хранит общее количество необходимых ходов.
  • Инициализируйте переменную, скажем, K как i и повторите цикл do-while, и в этом цикле обновите значение K до arr[K] и увеличьте значение count на 1 до тех пор, пока K не будет таким же, как значение i .
  • После выполнения вышеуказанных шагов выведите значение count как результирующее количество перемещений, необходимое для текущего индекса.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)