Dada una array (indexación basada en 1) arr[] de permutación de los primeros N números naturales , la tarea de cada elemento es encontrar la cantidad de movimientos necesarios para alcanzar ese índice de modo que en cada movimiento, el elemento de la array en el índice i se mueva al elemento de la array en el índice arr[i] .
Ejemplos:
Entrada: arr[] = {2, 3, 1}
Salida: 3 3 3
Explicación:
Para el elemento de array arr[1] = 2, el conjunto de movimientos de índices es 1 -> 2 -> 3 -> 1. El total el número de movimientos necesarios es 3.
Para el elemento de array arr[2] = 3, el conjunto de movimientos de índices es 2 -> 3 -> 1 -> 2. El número total de movimientos necesarios es 3.
Para el elemento de array arr[3 ] = 1, el conjunto de movimientos de índices es 3 -> 1 -> 2 -> 3. El recuento total de movimientos requerido es 3.Entrada: arr[] = {4, 6, 2, 1, 5, 3}
Salida: 2 3 3 2 1 3
Enfoque: el problema dado se puede resolver encontrando la cantidad de movimientos necesarios para cada elemento de la array para cada índice. Siga los pasos a continuación para resolver el problema dado:
- Recorra la array dada arr[] usando la variable i y realice los siguientes pasos:
- Inicializa una variable, digamos count , que almacena el número total de movimientos requeridos.
- Inicialice una variable, diga K como i e itere un ciclo do-while y en ese ciclo actualice el valor de K a arr[K] e incremente el valor de count en 1 hasta que K no sea el mismo que el valor de i .
- Después de completar los pasos anteriores, imprima el valor de conteo como el conteo resultante del movimiento requerido para el índice actual.
A continuación se muestra la implementación del enfoque anterior:
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 element
void 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 Code
int 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 approach
import 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 element def 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 Code arr = [4, 6, 2, 1, 5, 3] N = len(arr) numberOfPasses(arr, N) # This code is contributed by ihritik
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
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
Console.Write(cnt + " ");
}
}
// Driver Code
public 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>
2 3 3 2 1 3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA