Given an array(1-based indexing) arr[] of permutation of the first N natural numbers, the task for each element is to find the number of moves required to reach that index such that in each move, array element at index i moves to the array element at index arr[i].
Examples:
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
Approach: The given problem can be solved by finding the number of moves required for every array element for each index. Follow the steps below to solve the given problem:
- Traverse the given array arr[] using the variable i and perform the following steps:
- Initialize a variable, say count that stores the total number of moves required.
- Initialize a variable, say K as i and iterate a do-while loop and in that loop update the value of K to arr[K] and increment the value of count by 1 until K is not the same as the value of i.
- After completing the above steps, print the value of count as the resultant count of move required for the current index.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of moves// required to visit the same index// again for every array elementvoid numberOfPasses(vector<int> arr, int N){ // Make given array 0 index based for (int i = 0; i < N; ++i) { --arr[i]; } for (int i = 0; i < N; ++i) { // Stores the number of moves int cnt = 0; // Store index value int k = i; do { // Update the value of cnt ++cnt; // Make a pass k = arr[k]; } while (k != i); // Print the value of cnt cout << cnt << " "; }}// Driver Codeint main(){ vector<int> arr{ 4, 6, 2, 1, 5, 3 }; int N = arr.size(); numberOfPasses(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the number of moves // required to visit the same index // again for every array element static void numberOfPasses(int[] arr, int N) { // Make given array 0 index based for (int i = 0; i < N; ++i) { --arr[i]; } for (int i = 0; i < N; ++i) { // Stores the number of moves int cnt = 0; // Store index value int k = i; do { // Update the value of cnt ++cnt; // Make a pass k = arr[k]; } while (k != i); // Print the value of cnt System.out.print(cnt+" "); } } // Driver Code public static void main (String[] args) { int[] arr = { 4, 6, 2, 1, 5, 3 }; int N = arr.length; numberOfPasses(arr, N); }}// This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach# Function to find the number of moves# required to visit the same index# again for every array elementdef numberOfPasses(arr, N): # Make given array 0 index based for i in range(0, N): arr[i] = arr[i] - 1 for i in range(0, N): # Stores the number of moves cnt = 0; # Store index value k = i; while(True): # Update the value of cnt cnt = cnt + 1 # Make a pass k = arr[k] if (k == i): break; # Print the value of cnt print(cnt, end=" ") # Driver Codearr = [4, 6, 2, 1, 5, 3]N = len(arr)numberOfPasses(arr, N)# This code is contributed by ihritik |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the number of moves// required to visit the same index// again for every array elementstatic void numberOfPasses(int []arr, int N){ // Make given array 0 index based for (int i = 0; i < N; ++i) { --arr[i]; } for (int i = 0; i < N; ++i) { // Stores the number of moves int cnt = 0; // Store index value int k = i; do { // Update the value of cnt ++cnt; // Make a pass k = arr[k]; } while (k != i); // Print the value of cnt Console.Write(cnt + " "); }}// Driver Codepublic static void Main(){ int []arr = { 4, 6, 2, 1, 5, 3 }; int N = arr.Length; numberOfPasses(arr, N);}}// This code is contributed by Samim Hossain Mondal |
Javascript
<script> // JavaScript program for the above approach // Function to find the number of moves // required to visit the same index // again for every array element const numberOfPasses = (arr, N) => { // Make given array 0 index based for (let i = 0; i < N; ++i) { --arr[i]; } for (let i = 0; i < N; ++i) { // Stores the number of moves let cnt = 0; // Store index value let k = i; do { // Update the value of cnt ++cnt; // Make a pass k = arr[k]; } while (k != i); // Print the value of cnt document.write(`${cnt} `); } } // Driver Code let arr = [4, 6, 2, 1, 5, 3]; let N = arr.length; numberOfPasses(arr, N); // This code is contributed by rakeshsahni </script> |
Output
2 3 3 2 1 3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
