Dada una array de enteros arr[] que contiene una permutación de enteros de 1 a N . Sea K[] una array arbitraria. Cada elemento de la array arr[i] representa el índice del elemento en el que se coloca el elemento que se encuentra inicialmente en la posición ‘i’ de la array K[]. La tarea es encontrar el número de mezclas necesarias que se deben realizar en K[] para que los elementos vuelvan a la posición inicial.
Nota: se da que al menos se debe hacer 1 barajado sobre K[] (es decir), el elemento que está inicialmente en la posición ‘i’ en la array K[] debe colocarse en el índice arr[i] al menos una vez para todos los elementos del arreglo K[].
Ejemplos:
Entrada: arr[] = {3, 4, 1, 2}
Salida: 2 2 2 2
Explicación:
Sea el arreglo inicial B[] = {5, 6, 7, 8}. Por lo tanto:
Después de la primera reproducción aleatoria: el primer elemento irá a la tercera posición, el segundo elemento irá a la cuarta posición. Por lo tanto, B[] = {7, 8, 5, 6}.
Después de la segunda reproducción aleatoria: el primer elemento irá a la tercera posición, el segundo elemento irá a la cuarta posición. Por lo tanto, B[] = {5, 6, 7, 8}.
Por tanto, el número de barajes es 2 para que todos los elementos vuelvan a la misma posición inicial.
Entrada: arr[] = {4, 6, 2, 1, 5, 3}
Salida: 2 3 3 2 1 3
Enfoque ingenuo: El enfoque ingenuo para este problema es contar el número de barajas necesarias para cada elemento. La complejidad temporal para este enfoque sería O(N 2 ) .
Enfoque eficiente: un enfoque eficiente para este problema es calcular primero el número de ciclos en el problema. Los elementos en el mismo ciclo tienen el mismo número de mezclas. Por ejemplo, en la array dada arr[] = {3, 4, 1, 2}:
- En cada barajada, el primer elemento siempre va al tercer lugar y el tercer elemento siempre llega al primer lugar.
- Por lo tanto, se puede concluir que ambos elementos están en un ciclo. Por lo tanto, el número de mezclas tomadas para ambos elementos es 2, independientemente de cuál sea la array K[] .
- Por lo tanto, la idea es encontrar el número de dichos ciclos en la array y omitir esos elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the number of
// shuffles required for each element
// to return to its initial position
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// shuffles required for each element
// to return to its initial position
void countShuffles(int* A, int N)
{
// Initialize array to store
// the counts
int count[N];
// Initialize visited array to
// check if visited before or not
bool vis[N];
memset(vis, false, sizeof(vis));
// Making the array 0-indexed
for (int i = 0; i < N; i++)
A[i]--;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
// Initialize vector to store the
// elements in the same cycle
vector<int> cur;
// Initialize variable to store
// the current element
int pos = i;
// Count number of shuffles
// for current element
while (!vis[pos]) {
// Store the elements in
// the same cycle
cur.push_back(pos);
// Mark visited
vis[pos] = true;
// Make the shuffle
pos = A[pos];
}
// Store the result for all the
// elements in the same cycle
for (auto el : cur)
count[el] = cur.size();
}
}
// Print the result
for (int i = 0; i < N; i++)
cout << count[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 4, 6, 2, 1, 5, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
countShuffles(arr, N);
return 0;
}
Java
// Java program to find the number of
// shuffles required for each element
// to return to its initial position
import java.util.*;
class GFG {
// Function to count the number of
// shuffles required for each element
// to return to its initial position
static void countShuffles(int[] A, int N)
{
// Initialize array to store
// the counts
int[] count = new int[N];
// Initialize visited array to
// check if visited before or not
boolean[] vis = new boolean[N];
// Making the array 0-indexed
for(int i = 0; i < N; i++)
A[i]--;
for(int i = 0; i < N; i++)
{
if (!vis[i])
{
// Initialize vector to store the
// elements in the same cycle
Vector<Integer> cur = new Vector<>();
// Initialize variable to store
// the current element
int pos = i;
// Count number of shuffles
// for current element
while (!vis[pos])
{
// Store the elements in
// the same cycle
cur.add(pos);
// Mark visited
vis[pos] = true;
// Make the shuffle
pos = A[pos];
}
// Store the result for all the
// elements in the same cycle
for(int k = 0; k < cur.size(); k++)
count[cur.get(k)] = cur.size();
}
}
// Print the result
for(int k = 0; k < N; k++)
System.out.print(count[k] + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 4, 6, 2, 1, 5, 3 };
int N = arr.length;
countShuffles(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the number of # shuffles required for each element # to return to its initial position # Function to count the number of # shuffles required for each element # to return to its initial position def countShuffles(A, N): # Initialize array to store # the counts count = [0] * N # Initialize visited array to # check if visited before or not vis = [False] * N # Making the array 0-indexed for i in range(N): A[i] -= 1 for i in range(N): if (not vis[i]): # Initialize vector to store the # elements in the same cycle cur = [] # Initialize variable to store # the current element pos = i # Count number of shuffles # for current element while (not vis[pos]): # Store the elements in # the same cycle cur.append(pos) # Mark visited vis[pos] = True # Make the shuffle pos = A[pos] # Store the result for all the # elements in the same cycle for el in cur: count[el] = len(cur) # Print the result for i in range(N): print(count[i], end = " ") print() # Driver code if __name__ == "__main__": arr = [ 4, 6, 2, 1, 5, 3 ] N = len(arr) countShuffles(arr, N) # This code is contributed by chitranayal
C#
// C# program to find the number of
// shuffles required for each element
// to return to its initial position
using System;
using System.Collections;
class GFG{
// Function to count the number of
// shuffles required for each element
// to return to its initial position
static void countShuffles(int[] A, int N)
{
// Initialize array to store
// the counts
int[] count = new int[N];
// Initialize visited array to
// check if visited before or not
bool[] vis = new bool[N];
// Making the array 0-indexed
for(int i = 0; i < N; i++)
A[i]--;
for(int i = 0; i < N; i++)
{
if (!vis[i])
{
// Initialize vector to store the
// elements in the same cycle
ArrayList cur = new ArrayList();
// Initialize variable to store
// the current element
int pos = i;
// Count number of shuffles
// for current element
while (!vis[pos])
{
// Store the elements in
// the same cycle
cur.Add(pos);
// Mark visited
vis[pos] = true;
// Make the shuffle
pos = A[pos];
}
// Store the result for all the
// elements in the same cycle
for(int k = 0; k < cur.Count; k++)
count[(int)cur[k]] = cur.Count;
}
}
// Print the result
for(int k = 0; k < N; k++)
Console.Write(count[k] + " ");
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 4, 6, 2, 1, 5, 3 };
int N = arr.Length;
countShuffles(arr, N);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find the number of
// shuffles required for each element
// to return to its initial position
// Function to count the number of
// shuffles required for each element
// to return to its initial position
function countShuffles(A, N)
{
// Initialize array to store
// the counts
var count = Array(N);
// Initialize visited array to
// check if visited before or not
var vis = Array(N).fill(false);
// Making the array 0-indexed
for (var i = 0; i < N; i++)
A[i]--;
for (var i = 0; i < N; i++) {
if (!vis[i]) {
// Initialize vector to store the
// elements in the same cycle
var cur = [];
// Initialize variable to store
// the current element
var pos = i;
// Count number of shuffles
// for current element
while (!vis[pos]) {
// Store the elements in
// the same cycle
cur.push(pos);
// Mark visited
vis[pos] = true;
// Make the shuffle
pos = A[pos];
}
// Store the result for all the
// elements in the same cycle
for( var e1 = 0; e1<cur.length; e1++)
{
count[cur[e1]]=cur.length;
}
}
}
// Print the result
for (var i = 0; i < N; i++)
document.write( count[i] + " ");
document.write("<br>");
}
// Driver code
var arr = [ 4, 6, 2, 1, 5, 3 ];
var N = arr.length;
countShuffles(arr, N);
// This code is contributed by rrrtnx.
</script>
2 3 3 2 1 3
Complejidad de tiempo: O(N) , donde N es el tamaño de la array.
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA