Recuento de iteraciones para hacer que el mínimo sea 0 rotando el Array seguido de reducirlo del Array original

Dada una array arr[]. La tarea es encontrar el número de iteraciones requeridas para hacer que el elemento mínimo en la array sea 0 . En una iteración, gire a la izquierda la array en uno y reste el elemento correspondiente de la array original y la array rotada.

Ejemplos:

Entrada: arr[] = { 2, 6, 3, 4, 8, 7 }
Salida: 3
Explicación: Consulte la imagen a continuación para obtener una explicación.

Entrada: arr[] = { 4, 10, 12, 3, 9, 7 }
Salida: 5

Enfoque ingenuo: la forma más fácil de resolver este problema es utilizando el enfoque codicioso .

• Simplemente extraiga el primer elemento de la array y agréguelo al final y luego realice la resta en el elemento correspondiente.
• De manera similar, realice la misma operación en la array resultante hasta que obtengamos el elemento mínimo en una array como cero y devuelva el recuento de iteraciones.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find no of iterations.
int minZero(vector<int>& A, int n)
{
 
    // Initialize count c = 0.
    int c = 0;
 
    // if zero is already present
    // in array return c.
    if (*min_element(A.begin(), A.end()) == 0)
        return c;
 
    // Iterate till minimum
    // in array becomes zero.
    while (*min_element(A.begin(), A.end()) != 0) {
 
        // Copy array element to A1
        vector<int> A1 = A;
 
        // Pop first element and
        // append it to last
        int x = A[0];
        A.erase(A.begin());
        A.push_back(x);
 
        // Perform subtraction
        for (int i = 0; i < n; i++)
            A[i] = abs(A[i] - A1[i]);
 
        // Increment count by 1
        c += 1;
    }
 
    // Return value of count c
    return c;
}
 
// Driver Code
int main()
{
   
    // Original array
    vector<int> arr = { 2, 6, 3, 4, 8, 7 };
 
    // Calling method minZero
    int x = minZero(arr, arr.size());
 
    // Print the result
    cout << (x);
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

// Java program for above approach
import java.util.*;
 
class GFG{
 
  // Function to find no of iterations.
  static int minZero(Vector<Integer> A, int n)
  {
 
    // Initialize count c = 0.
    int c = 0;
 
    // if zero is already present
    // in array return c.
    if (Collections.min(A) == 0)
      return c;
 
    // Iterate till minimum
    // in array becomes zero.
    while (Collections.min(A) != 0) {
 
      // Copy array element to A1
      Vector<Integer> A1 = (Vector<Integer>) A.clone();
 
      // Pop first element and
      // append it to last
      int x = A.get(0);
      A.remove(0);
      A.add(x);
 
      // Perform subtraction
      for (int i = 0; i < n; i++)
        A.set(i, Math.abs(A.get(i) - A1.get(i)));
 
      // Increment count by 1
      c += 1;
    }
 
    // Return value of count c
    return c;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Original array
    Integer []arr = { 2, 6, 3, 4, 8, 7 };
    Vector<Integer> v = new Vector<Integer>();
    Collections.addAll(v, arr);
     
    // Calling method minZero
    int x = minZero(v, arr.length);
 
    // Print the result
    System.out.print(x);
 
  }
}
 
// This code is contributed by 29AjayKumar

# Python program for above approach
 
# Function to find no of iterations.
def minZero(A, n):
 
    # Initialize count c = 0.
    c = 0
 
    # if zero is already present
    # in array return c.
    if min(A) == 0:
        return c
 
    # Iterate till minimum
    # in array becomes zero.
    while min(A) != 0:
 
        # Copy array element to A1
        A1 = A[:]
 
        # Pop first element and
        # append it to last
        x = A.pop(0)
        A.append(x)
 
        # Perform subtraction
        for i in range(n):
            A[i] = abs(A[i]-A1[i])
 
        # Increment count by 1
        c += 1
 
    # Return value of count c
    return c
 
# Driver Code
 
# Original array
arr = [2, 6, 3, 4, 8, 7]
 
# Calling method minZero
x = minZero(arr, len(arr))
 
# Print the result
print(x)

// C# program for above approach
using System;
using System.Linq;
class GFG{
 
  // Function to find no of iterations
  static int minZero(int []A, int n)
  {
 
    // Initialize count c = 0
    int c = 0;
 
    // If 0 already in array return c
 
    if (A.Min()== 0)
      return c;
 
    // Iterate till we get zero in array
    while (A.Min() != 0) {
 
      // Assign first element in x
      int x = (int)A[0];
 
      // Loop to subtract consecutive element
      for (int i = 0; i < (n - 1); i++) {
        A[i] = Math.Abs((int)A[i] - (int)A[i + 1]);
      }
      A[n - 1] = Math.Abs((int)A[n - 1] - x);
 
      // Increment count c
      c += 1;
    }
 
    // Return c
    return c;
  }
 
  // Driver Code
  public static void Main()
  {
 
    // Original array
    int []arr = { 2, 6, 3, 4, 8, 7 };
 
    // Length of array
    int N = arr.Length;
 
    // calling function
    int x = minZero(arr, N);
 
    // print the result
    Console.Write(x);
  }
}
 
// This code is contributed by avijitmondal1998

<script>
// Javascript program for above approach
 
// Function to find no of iterations.
function minZero(A, n){
 
    // Initialize count c = 0.
    let c = 0
    let _A = [...A].sort((a, b) => a - b);
 
    // if zero is already present
    // in array return c.
    if ([...A].sort((a, b) => a - b)[0] == 0)
        return c
 
    // Iterate till minimum
    // in array becomes zero.
    while ([...A].sort((a, b) => a - b)[0] != 0){
 
        // Copy array element to A1
        let A1 = [...A]
 
        // Pop first element and
        // append it to last
        let x = A[0];
        A.shift();
        A.push(x)
 
        // Perform subtraction
        for(let i = 0; i < n; i++)
            A[i] = Math.abs(A[i]-A1[i])
 
        // Increment count by 1
        c += 1
    }
 
    // Return value of count c
    return c
}
 
// Driver Code
 
// Original array
let arr = [2, 6, 3, 4, 8, 7]
 
// Calling method minZero
let x = minZero(arr, arr.length)
 
// Print the result
document.write(x)
 
// This code is contributed by gfgking.
 
</script>

3

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

Enfoque eficiente: un enfoque optimizado para el espacio es un enfoque lógico y basado en la implementación. Siga los pasos a continuación para resolver el problema dado. 

• Almacene el primer elemento de la array en la variable x .
• Ahora encuentre la diferencia absoluta entre elementos consecutivos.
• Reemplace el resultado del índice 0 .
• Reste el último elemento de la variable x y guárdelo.
• cuente la iteración y repita los pasos.
• Regresa el conteo como la respuesta final.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find no of iterations
int minZero(int A[], int n)
{
 
    // Initialize count c = 0
    int c = 0;
 
    // If 0 already in array return c
 
    if (*min_element(A + 0, A + n - 1) == 0)
        return c;
 
    // Iterate till we get zero in array
    while (*min_element(A + 0, A + n - 1) != 0) {
 
        // Assign first element in x
        int x = A[0];
 
        // Loop to subtract consecutive element
        for (int i = 0; i < (n - 1); i++) {
            A[i] = abs(A[i] - A[i + 1]);
        }
        A[n - 1] = abs(A[n - 1] - x);
 
        // Increment count c
        c += 1;
    }
 
    // Return c
    return c;
}
 
// Driver Code
int main()
{
   
    // Original array
    int arr[] = { 2, 6, 3, 4, 8, 7 };
 
    // Length of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // calling function
    int x = minZero(arr, N);
 
    // print the result
    cout << (x);
}
 
// This code is contributed by ukasp.

// Java program for above approach
import java.util.*;
class GFG{
 
// Function to find no of iterations
static int minZero(int A[], int n)
{
 
    // Initialize count c = 0
    int c = 0;
 
    // If 0 already in array return c
 
    if (Arrays.stream(A).min().getAsInt()== 0)
        return c;
 
    // Iterate till we get zero in array
    while (Arrays.stream(A).min().getAsInt() != 0) {
 
        // Assign first element in x
        int x = A[0];
 
        // Loop to subtract consecutive element
        for (int i = 0; i < (n - 1); i++) {
            A[i] = Math.abs(A[i] - A[i + 1]);
        }
        A[n - 1] = Math.abs(A[n - 1] - x);
 
        // Increment count c
        c += 1;
    }
 
    // Return c
    return c;
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Original array
    int arr[] = { 2, 6, 3, 4, 8, 7 };
 
    // Length of array
    int N = arr.length;
 
    // calling function
    int x = minZero(arr, N);
 
    // print the result
    System.out.print(x);
}
 
}
 
// This code is contributed by 29AjayKumar

# Python program for above approach
 
# Function to find no of iterations
def minZero(A, n):
 
    # Initialize count c = 0
    c = 0
 
    # If 0 already in array return c
    if min(A) == 0:
        return c
 
    # Iterate till we get zero in array
    while min(A) != 0:
 
        # Assign first element in x
        x = A[0]
 
        # Loop to subtract consecutive element
        for i in range(n-1):
            A[i] = abs(A[i]-A[i + 1])
        A[n-1] = abs(A[n-1]-x)
 
        # Increment count c
        c += 1
 
    # Return c
    return c
 
# Driver Code
 
# Original array
arr = [2, 6, 3, 4, 8, 7]
 
# Length of array
N = len(arr)
 
# calling function
x = minZero(arr, N)
 
# print the result
print(x)

// C# program for above approach
using System;
using System.Linq;
class GFG{
 
// Function to find no of iterations
static int minZero(int []A, int n)
{
 
    // Initialize count c = 0
    int c = 0;
 
    // If 0 already in array return c
 
    if (A.Min()== 0)
        return c;
 
    // Iterate till we get zero in array
    while (A.Min() != 0) {
 
        // Assign first element in x
        int x = (int)A[0];
 
        // Loop to subtract consecutive element
        for (int i = 0; i < (n - 1); i++) {
            A[i] = Math.Abs((int)A[i] - (int)A[i + 1]);
        }
        A[n - 1] = Math.Abs((int)A[n - 1] - x);
 
        // Increment count c
        c += 1;
    }
 
    // Return c
    return c;
}
 
// Driver Code
public static void Main()
{
   
    // Original array
    int []arr = { 2, 6, 3, 4, 8, 7 };
 
    // Length of array
    int N = arr.Length;
 
    // calling function
    int x = minZero(arr, N);
 
    // print the result
    Console.Write(x);
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
        // JavaScript code for the above approach
 
 
        // Function to find no of iterations
        function minZero(A, n) {
 
            // Initialize count c = 0
            let c = 0
 
            // If 0 already in array return c
            if (Math.min(...A) == 0)
                return c
 
            // Iterate till we get zero in array
            while (Math.min(...A) != 0) {
 
                // Assign first element in x
                let x = A[0]
 
                // Loop to subtract consecutive element
                for (let i = 0; i < n - 1; i++) {
                    A[i] = Math.abs(A[i] - A[i + 1])
                }
                A[n - 1] = Math.abs(A[n - 1] - x)
 
                // Increment count c
                c += 1
            }
             
            // Return c
            return c
        }
         
        // Driver Code
 
        // Original array
        let arr = [2, 6, 3, 4, 8, 7]
 
        // Length of array
        let N = arr.length
 
        // calling function
        let x = minZero(arr, N)
 
        // print the result
        document.write(x)
         
  // This code is contributed by Potta Lokesh
    </script>

3

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