Cuente las rotaciones de array en el sentido de las agujas del reloj necesarias para maximizar el recuento de elementos de array presentes en índices iguales a su valor

Dada una array arr[] que consiste en una permutación de los primeros N números naturales, la tarea es encontrar el número mínimo de rotaciones circulares en el sentido de las manecillas del reloj requeridas para maximizar la cantidad de elementos que satisfacen la condición arr[i] = i ( 1- indexación basada ) donde 1 ≤ i ≤ N .

Ejemplos:

Entrada: arr[] = {4, 5, 1, 2, 3}
Salida: 3
Explicación: Al rotar la array tres veces, la array se modifica a {1, 2, 3, 4, 5}. Todos los elementos del arreglo satisfacen la condición arr[i] = i.

Entrada: arr[] = {3, 4, 1, 5, 2}
Salida: 2
Explicación: Al rotar la array dos veces, la array se modifica a {5, 2, 3, 4, 1}. Tres elementos del arreglo satisfacen la condición arr[i] = i, que es el máximo posible para el arreglo dado.

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice dos enteros maxi y ans , y dos arrays new_arr[] y freq[] .
• Recorra la array arr[] an para cada elemento, cuente el número de índices que lo separan de su posición correcta, es decir, |(arr[i] – i + N) % N| .
• Almacene los recuentos de cada elemento de la array en una nueva array new_arr[] .
• Almacene el conteo de frecuencias de cada elemento en new_arr[] en el arreglo freq[] .
• Imprima el elemento con la frecuencia máxima como la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// clockwise array rotations required
// to maximize count of array elements
// present at indices same as their value
void find_min_rot(int arr[], int n)
{
    // Stores count of indices separating
    // elements from its correct position
    int new_arr[n + 1];
    int maxi = 1, ans = 0;
 
    // Stores frequencies of counts of
    // indices separating
    int freq[n + 1];
    for (int i = 1; i <= n; i++) {
        freq[i] = 0;
    }
 
    // Count indices separating each
    // element from its correct position
    for (int i = 1; i <= n; i++) {
 
        new_arr[i] = (arr[i] - i + n) % n;
    }
 
    // Update frequencies of counts obtained
    for (int i = 1; i <= n; i++) {
 
        freq[new_arr[i]]++;
    }
 
    // Find the count with maximum frequency
    for (int i = 1; i <= n; i++) {
        if (freq[i] > maxi) {
            maxi = freq[i];
            ans = i;
        }
    }
 
    // Print the answer
    cout << ans << endl;
}
 
// Driver Code
int main()
{
 
    int N = 5;
    int arr[] = { -1, 3, 4, 1, 5, 2 };
 
    // Find minimum number of
    // array rotations required
    find_min_rot(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
    
class GFG{
    
// Function to count the number of
// clockwise array rotations required
// to maximize count of array elements
// present at indices same as their value
static void find_min_rot(int arr[], int n)
{
     
    // Stores count of indices separating
    // elements from its correct position
    int[] new_arr = new int[n + 1];
    int maxi = 1, ans = 0;
  
    // Stores frequencies of counts of
    // indices separating
    int[] freq = new int[n + 1];
    for(int i = 1; i <= n; i++)
    {
        freq[i] = 0;
    }
  
    // Count indices separating each
    // element from its correct position
    for(int i = 1; i <= n; i++)
    {
        new_arr[i] = (arr[i] - i + n) % n;
    }
  
    // Update frequencies of counts obtained
    for(int i = 1; i <= n; i++)
    {
        freq[new_arr[i]]++;
    }
  
    // Find the count with maximum frequency
    for(int i = 1; i <= n; i++)
    {
        if (freq[i] > maxi)
        {
            maxi = freq[i];
            ans = i;
        }
    }
  
    // Print the answer
    System.out.print(ans);
}
    
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    int[] arr = { -1, 3, 4, 1, 5, 2 };
  
    // Find minimum number of
    // array rotations required
    find_min_rot(arr, N);
}
}
 
// This code is contributed by sanjoy_62

# Python3 program for the above approach
  
# Function to count the number of
# clockwise array rotations required
# to maximize count of array elements
# present at indices same as their value
def find_min_rot(arr, n):
     
    # Stores count of indices separating
    # elements from its correct position
    new_arr = [0] * (n + 1)
    maxi = 1
    ans = 0
  
    # Stores frequencies of counts of
    # indices separating
    freq = [0] * (n + 1)
    for i in range(1, n + 1):
        freq[i] = 0
  
    # Count indices separating each
    # element from its correct position
    for i in range(1, n + 1):
         new_arr[i] = (arr[i] - i + n) % n
  
    # Update frequencies of counts obtained
    for i in range(1, n + 1):
        freq[new_arr[i]] += 1
  
    # Find the count with maximum frequency
    for i in range(1, n + 1):
        if (freq[i] > maxi):
            maxi = freq[i]
            ans = i
             
    # Print the answer
    print(ans)
  
# Driver Code
if __name__ == '__main__':
  
    N = 5
    arr = [ -1, 3, 4, 1, 5, 2 ]
  
    # Find minimum number of
    # array rotations required
    find_min_rot(arr, N)
     
# This code is contributed by jana_sayantan

// C# program for the above approach
using System;
 
class GFG
{
    
// Function to count the number of
// clockwise array rotations required
// to maximize count of array elements
// present at indices same as their value
static void find_min_rot(int []arr, int n)
{
     
    // Stores count of indices separating
    // elements from its correct position
    int[] new_arr = new int[n + 1];
    int maxi = 1, ans = 0;
  
    // Stores frequencies of counts of
    // indices separating
    int[] freq = new int[n + 1];
    for(int i = 1; i <= n; i++)
    {
        freq[i] = 0;
    }
  
    // Count indices separating each
    // element from its correct position
    for(int i = 1; i <= n; i++)
    {
        new_arr[i] = (arr[i] - i + n) % n;
    }
  
    // Update frequencies of counts obtained
    for(int i = 1; i <= n; i++)
    {
        freq[new_arr[i]]++;
    }
  
    // Find the count with maximum frequency
    for(int i = 1; i <= n; i++)
    {
        if (freq[i] > maxi)
        {
            maxi = freq[i];
            ans = i;
        }
    }
  
    // Print the answer
    Console.Write(ans);
}
    
// Driver Code
public static void Main(String[] args)
{
    int N = 5;
    int[] arr = { -1, 3, 4, 1, 5, 2 };
  
    // Find minimum number of
    // array rotations required
    find_min_rot(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript implementation of the above approach
 
// Function to count the number of
// clockwise array rotations required
// to maximize count of array elements
// present at indices same as their value
function find_min_rot(arr, n)
{
      
    // Stores count of indices separating
    // elements from its correct position
    let new_arr = [];
    let maxi = 1, ans = 0;
   
    // Stores frequencies of counts of
    // indices separating
    let freq = [];
    for(let i = 1; i <= n; i++)
    {
        freq[i] = 0;
    }
   
    // Count indices separating each
    // element from its correct position
    for(let i = 1; i <= n; i++)
    {
        new_arr[i] = (arr[i] - i + n) % n;
    }
   
    // Update frequencies of counts obtained
    for(let i = 1; i <= n; i++)
    {
        freq[new_arr[i]]++;
    }
   
    // Find the count with maximum frequency
    for(let i = 1; i <= n; i++)
    {
        if (freq[i] > maxi)
        {
            maxi = freq[i];
            ans = i;
        }
    }
   
    // Print the answer
    document.write(ans);
}
 
// Driver code
    let N = 5;
    let arr = [ -1, 3, 4, 1, 5, 2 ];
   
    // Find minimum number of
    // array rotations required
    find_min_rot(arr, N);
      
     // This code is contributed by code_hunt.
</script>

2

Complejidad temporal: O(N)
Espacio auxiliar: O(N)