Rotaciones mínimas que tienen elementos máximos con valor como máximo su índice

Dada una array arr[] de tamaño N , la array se puede rotar cualquier número de veces, de modo que después de la rotación, cada elemento de la array arr[] que sea menor o igual que su índice obtendrá 1 punto. La tarea es encontrar el índice de rotación K que corresponde a la puntuación más alta. Si hay varias respuestas, devuelva la más pequeña entre todas.

Ejemplos:

Entrada: arr[] = {2, 3, 1, 4, 0}
Salida: 3
Explicación: 
k = 0, arr = [2,3,1,4,0], puntuación 2
k = 1, arr = [3 ,1,4,0,2], puntuación 3 [índice numérico: 3>1, 1==1(1 punto), 4>2, 0<3 (1 punto), 2<4 (1 punto)]
k = 2, arr = [1,4,0,2,3], puntuación 3
k = 3, arr = [4,0,2,3,1], puntuación 4
k = 4, arr = [0,2, 3,1,4], puntuación 3
por lo tanto K = 3, da la puntuación más alta.

Entrada: arr[] = {0, 0, 2, 4, 6}
Salida: 4

Enfoque ingenuo: calcule las puntuaciones para cada rotación. Luego busque la puntuación más alta entre las puntuaciones totales calculadas y devuelva el índice más bajo si hay varias puntuaciones.

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 rotate the array
void rotate(vector<int>& arr, int N)
{
    int temp = arr[0], i;
    for (i = 0; i < N - 1; i++)
        arr[i] = arr[i + 1];
    arr[N - 1] = temp;
    return;
}
 
// Function to calculate the
// total score of a rotation
int calculate(vector<int>& arr)
{
    int score = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] <= i) {
            score++;
        }
    }
    return score;
}
 
// Function to find the rotation index k
// that corresponds to the highest score
int bestIndex(vector<int>& nums)
{
    int N = nums.size();
    int high_score = -1;
    int min_idx = 0;
 
    for (int i = 0; i < N; i++) {
        if (i != 0)
            // Rotates the array to left
            // by one position.
            rotate(nums, N);
 
        // Stores score of current rotation
        int cur_score = calculate(nums);
 
        if (cur_score > high_score) {
            min_idx = i;
            high_score = cur_score;
        }
    }
    return min_idx;
}
 
// Driver code
int main()
{
    vector<int> arr = { 2, 3, 1, 4, 0 };
    cout << bestIndex(arr);
    return 0;
}

// Java program for the above approach
class GFG {
 
  // Function to rotate the array
  static void rotate(int[] arr, int N) {
    int temp = arr[0], i;
    for (i = 0; i < N - 1; i++)
      arr[i] = arr[i + 1];
    arr[N - 1] = temp;
    return;
  }
 
  // Function to calculate the
  // total score of a rotation
  static int calculate(int[] arr) {
    int score = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] <= i) {
        score++;
      }
    }
    return score;
  }
 
  // Function to find the rotation index k
  // that corresponds to the highest score
  static int bestIndex(int[] nums) {
    int N = nums.length;
    int high_score = -1;
    int min_idx = 0;
 
    for (int i = 0; i < N; i++) {
      if (i != 0)
 
        // Rotates the array to left
        // by one position.
        rotate(nums, N);
 
      // Stores score of current rotation
      int cur_score = calculate(nums);
 
      if (cur_score > high_score) {
        min_idx = i;
        high_score = cur_score;
      }
    }
    return min_idx;
  }
 
  // Driver code
  public static void main(String args[]) {
    int[] arr = { 2, 3, 1, 4, 0 };
    System.out.println(bestIndex(arr));
  }
}
 
// This code is contributed by Saurabh Jaiswal

# Python program for the above approach
 
# Function to rotate the array
def rotate(arr, N):
 
    temp = arr[0]
    for i in range(0, N-1):
        arr[i] = arr[i + 1]
    arr[N - 1] = temp
    return
 
# Function to calculate the
# total score of a rotation
def calculate(arr):
 
    score = 0
    for i in range(0, len(arr)):
        if (arr[i] <= i):
            score = score + 1
 
    return score
 
# Function to find the rotation index k
# that corresponds to the highest score
def bestIndex(nums):
 
    N = len(nums)
    high_score = -1
    min_idx = 0
 
    for i in range(0, N):
        if (i != 0):
           
            # Rotates the array to left
            # by one position.
            rotate(nums, N)
 
        # Stores score of current rotation
        cur_score = calculate(nums)
 
        if (cur_score > high_score):
            min_idx = i
            high_score = cur_score
 
    return min_idx
 
# Driver code
arr = [2, 3, 1, 4, 0]
print(bestIndex(arr))
 
# This code is contributed by Taranpreet

// C# program for the above approach
using System;
class GFG
{
 
  // Function to rotate the array
  static void rotate(int[] arr, int N)
  {
    int temp = arr[0], i;
    for (i = 0; i < N - 1; i++)
      arr[i] = arr[i + 1];
    arr[N - 1] = temp;
    return;
  }
 
  // Function to calculate the
  // total score of a rotation
  static int calculate(int[] arr)
  {
    int score = 0;
    for (int i = 0; i < arr.Length; i++) {
      if (arr[i] <= i) {
        score++;
      }
    }
    return score;
  }
 
  // Function to find the rotation index k
  // that corresponds to the highest score
  static int bestIndex(int[] nums)
  {
    int N = nums.Length;
    int high_score = -1;
    int min_idx = 0;
 
    for (int i = 0; i < N; i++) {
      if (i != 0)
        // Rotates the array to left
        // by one position.
        rotate(nums, N);
 
      // Stores score of current rotation
      int cur_score = calculate(nums);
 
      if (cur_score > high_score) {
        min_idx = i;
        high_score = cur_score;
      }
    }
    return min_idx;
  }
 
  // Driver code
  public static void Main()
  {
    int[] arr = { 2, 3, 1, 4, 0 };
    Console.Write(bestIndex(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to rotate the array
       function rotate(arr, N) {
           let temp = arr[0], i;
           for (i = 0; i < N - 1; i++)
               arr[i] = arr[i + 1];
           arr[N - 1] = temp;
           return arr;
       }
 
       // Function to calculate the
       // total score of a rotation
       function calculate(arr) {
           let score = 0;
           for (let i = 0; i < arr.length; i++) {
               if (arr[i] <= i) {
                   score++;
               }
           }
           return score;
       }
 
       // Function to find the rotation index k
       // that corresponds to the highest score
       function bestIndex(nums) {
           let N = nums.length;
           let high_score = -1;
           let min_idx = 0;
 
           for (let i = 0; i < N; i++) {
               if (i != 0)
                   // Rotates the array to left
                   // by one position.
                   nums = [...rotate(nums, N)];
 
               // Stores score of current rotation
               let cur_score = calculate(nums);
 
               if (cur_score > high_score) {
                   min_idx = i;
                   high_score = cur_score;
               }
           }
           return min_idx;
       }
 
       // Driver code
 
       let arr = [2, 3, 1, 4, 0];
       document.write(bestIndex(arr));
 
      // This code is contributed by Potta Lokesh
   </script>

3

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: En este enfoque, 

• primero calcule la puntuación de entrada y luego haga una cola de prioridad ( q ) en orden ascendente.
• Luego coloque todas las diferencias no negativas de i – arr[i] , digamos diff en la cola de prioridad.
• Después de esto, atraviese de 1 a (N -1) . Cada vez que se realiza el cambio, dado que es un cambio a la izquierda, arr[i-1] se convierte en la cola de arr y arr[i-1] se convierte en arr[N-1] .
• Además, todo el diff[i] se convierte en diff[i] -1 por la disminución del índice del mapa (causado por el desplazamiento a la izquierda).
• Luego, la puntuación se cambiará en 2 casos después de cada rotación:

Caso 1: 
arr[i-1] <= N -1, luego puntuación++;

Caso 2: 
i > q.front(), luego puntúe–

porque significa que el cambio hace que algunos valores diferenciales se vuelvan negativos (que originalmente no son negativos). 

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 find the rotation index k
// that corresponds to the highest score
int bestIndex(vector<int>& nums)
{
    int N = nums.size();
    int gain = 0;
    int idx;
    priority_queue<int, vector<int>, greater<int> > q;
 
    for (int i = 0; i < N; i++) {
        int diff = i - nums[i];
        if (diff >= 0) {
            gain++;
            q.push(diff);
        }
    }
 
    int current = gain;
    idx = 0;
 
    for (int i = 1; i <= N - 1; i++) {
        while (!q.empty() && (i > q.top())) {
            q.pop();
            current--;
        }
        if (nums[i - 1] <= (N - 1)) {
            current++;
            q.push(i + (N - 1) - nums[i - 1]);
        }
        if (current > gain) {
            idx = i;
            gain = current;
        }
    }
    return idx;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 2, 3, 1, 4, 0 };
    cout << bestIndex(arr);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
public class GFG
{
 
  // Function to find the rotation index k
  // that corresponds to the highest score
  static int bestIndex(int[] nums)
  {
    int N = nums.length;
    int gain = 0;
    int idx = 0;
    PriorityQueue<Integer> q
      = new PriorityQueue<Integer>();
 
    for (int i = 0; i < N; i++) {
      int diff = i - nums[i];
      if (diff >= 0) {
        gain++;
        q.add(diff);
      }
    }
 
    int current = gain;
    idx = 0;
 
    for (int i = 1; i <= N - 1; i++) {
      while (q.isEmpty() == false && (i > q.peek())) {
        q.remove();
        current--;
      }
      if (nums[i - 1] <= (N - 1)) {
        current++;
        q.add(i + (N - 1) - nums[i - 1]);
      }
      if (current > gain) {
        idx = i;
        gain = current;
      }
    }
    return idx;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int[] arr = { 2, 3, 1, 4, 0 };
    System.out.print(bestIndex(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

// C# program of the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find the rotation index k
  // that corresponds to the highest score
  static int bestIndex(int[] nums)
  {
    int N = nums.Length;
    int gain = 0;
    int idx = 0;
    List<int> q = new List<int>();
 
    for (int i = 0; i < N; i++) {
      int diff = i - nums[i];
      if (diff >= 0) {
        gain++;
        q.Add(diff);
        q.Sort();
        q.Reverse();
      }
    }
 
    int current = gain;
    idx = 0;
 
    for (int i = 1; i <= N - 1; i++) {
      while (i > q[0]) {
        q.RemoveAt(0);
        current--;
      }
      if (nums[i - 1] <= (N - 1)) {
        current++;
        q.Add(i + (N - 1) - nums[i - 1]);
        q.Sort();
        q.Reverse();
      }
      if (current > gain) {
        idx = i;
        gain = current;
      }
    }
    return idx-1;
  }
 
  // Driver Code
  public static void Main()
  {
    int[] arr = { 2, 3, 1, 4, 0 };
    Console.Write(bestIndex(arr));
  }
}
 
// This code is contributed by sanjoy_62.

<script>
    // JavaScript code for the above approach
 
  // Function to find the rotation index k
  // that corresponds to the highest score
  function bestIndex(nums)
  {
    let N = nums.length;
    let gain = 0;
    let idx = 0;
    let q = [];
 
    for (let i = 0; i < N; i++) {
      let diff = i - nums[i];
      if (diff >= 0) {
        gain++;
        q.push(diff);
      }
    }
 
    let current = gain;
    idx = 0;
 
    for (let i = 1; i <= N - 1; i++) {
      while (q.length == false && (i > (q[q.length - 1]))) {
        q.shift();
        current--;
      }
      if (nums[i - 1] <= (N - 1)) {
        current++;
        q.push(i + (N - 1) - nums[i - 1]);
      }
      if (current > gain) {
        idx = i;
        gain = current;
      }
    }
    return idx-1;
  }
 
    // Driver Code
    let arr = [ 2, 3, 1, 4, 0 ];
    document.write(bestIndex(arr));
 
// This code is contributed by code_hunt.
</script>

3

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