Número mínimo de decrementos por 1 necesarios para reducir todos los elementos de una array circular a 0

Dada una array circular arr[] que consta de N enteros, la tarea es encontrar el número mínimo de operaciones para reducir todos los elementos de una array circular a 0 . En cada operación, reduce el elemento actual en 1 ( comenzando desde el primer elemento ) y pasa al siguiente elemento.

Ejemplos:

Entrada: arr[] = {2, 0, 2}
Salida: 6
Explicación: Las
siguientes son las operaciones realizadas:

1. Reducir el elemento de la array arr[0] en 1 modifica la array a { 1 , 0, 2} y pasar al siguiente elemento arr[1].
2. No haga nada y pase al siguiente elemento, es decir, arr[2].
3. Reducir el elemento de array arr[2] en 1 modifica la array a {1, 0, 1 } y pasar al siguiente elemento arr[0].
4. Reducir el elemento de array arr[0] en 1 modifica la array a { 0 , 0, 1} y pasar al siguiente elemento arr[1].
5. No haga nada y pase al siguiente elemento, es decir, arr[2].
6. Reducir el elemento de array arr[2] en 1 modifica la array a {0, 0, 0 } y pasar al siguiente elemento arr[0].

Después de las operaciones anteriores, todos los elementos de la array circular se han reducido a 0. Por lo tanto, el número mínimo de operaciones requeridas es 6.

Entrada: arr[] = {0, 3, 1, 3, 2}
Salida: 14

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es atravesar la array dada en un orden circular realizando las operaciones dadas hasta que todos los elementos de la array sean 0 y llevar la cuenta de las operaciones realizadas. Después de completar los pasos anteriores, imprima el número de operaciones realizadas.

Complejidad temporal: O(N*M), donde M es el elemento máximo del arreglo .
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar al encontrar el último índice del elemento de array máximo y encontrar el número mínimo de operaciones requeridas en consecuencia. Siga los pasos a continuación para resolver el problema:

• Inicialice dos variables, digamos pos y M que almacena el último índice del elemento máximo y el elemento máximo respectivamente.
• Recorre la array dada usando la variable i y si el valor de arr[i] es al menos M , entonces modifica el valor de M como arr[i] y pos como i .
• Después de completar los pasos anteriores, imprima el valor de (mx – 1)*N + pos +1 como el número mínimo de pasos resultante.

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 minimum operation
// require to make all elements 0
void minimumOperations(int arr[], int N)
{
    // Stores the maximum element and
    // its position in the array
    int mx = 0, pos = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Update the maximum element
        // and its index
        if (arr[i] >= mx) {
            mx = arr[i];
            pos = i;
        }
    }
 
    // Print the minimum number of
    // operations required
    cout << (mx - 1) * N + pos + 1;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 0, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    minimumOperations(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
 
  // Function to find minimum operation
  // require to make all elements 0
  static void minimumOperations(int arr[], int N)
  {
 
    // Stores the maximum element and
    // its position in the array
    int mx = 0, pos = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Update the maximum element
      // and its index
      if (arr[i] >= mx) {
        mx = arr[i];
        pos = i;
      }
    }
 
    // Print the minimum number of
    // operations required
    System.out.println((mx - 1) * N + pos + 1);
  }
 
  // Driver Code
  public static void main (String[] args)
  {
    int arr[] = { 2, 0, 2 };
    int N = arr.length;
 
    minimumOperations(arr, N);
  }
}
 
// This code is contributed by Potta Lokesh

# Python3 program for the above approach
 
# Function to find minimum operation
# require to make all elements 0
def minimumOperations(arr, N):
     
    # Stores the maximum element and
    # its position in the array
    mx = 0
    pos = 0
 
    # Traverse the array
    for i in range(N):
         
        # Update the maximum element
        # and its index
        if (arr[i] >= mx):
            mx = arr[i]
            pos = i
 
    # Print the minimum number of
    # operations required
    print((mx - 1) * N + pos + 1)
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 2, 0, 2 ]
    N = len(arr)
     
    minimumOperations(arr, N)
 
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
 
class GFG{
 
  // Function to find minimum operation
  // require to make all elements 0
  static void minimumOperations(int[] arr, int N)
  {
 
    // Stores the maximum element and
    // its position in the array
    int mx = 0, pos = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Update the maximum element
      // and its index
      if (arr[i] >= mx) {
        mx = arr[i];
        pos = i;
      }
    }
 
    // Print the minimum number of
    // operations required
    Console.Write((mx - 1) * N + pos + 1);
  }
 
// Driver Code
public static void Main()
{
    int[] arr = { 2, 0, 2 };
    int N = arr.Length;
 
    minimumOperations(arr, N);
}
}
 
// This code is contributed by splevel62.

<script>
 
// JavaScript code for above approach
 
  // Function to find minimum operation
  // require to make all elements 0
  function minimumOperations(arr, N)
  {
 
    // Stores the maximum element and
    // its position in the array
    let mx = 0, pos = 0;
 
    // Traverse the array
    for (let i = 0; i < N; i++) {
 
      // Update the maximum element
      // and its index
      if (arr[i] >= mx) {
        mx = arr[i];
        pos = i;
      }
    }
 
    // Print the minimum number of
    // operations required
    document.write((mx - 1) * N + pos + 1);
  }
 
// Driver Code
    let arr = [ 2, 0, 2 ];
    let N = arr.length;
 
    minimumOperations(arr, N);
     
    // This code is contributed by sanjoy_62.
</script>

6

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