Número mínimo de pasos para hacer que todos los elementos de la array sean iguales

Dados dos arreglos A[] y B[] de la misma longitud, la tarea es encontrar el número mínimo de pasos necesarios para igualar todos los elementos del arreglo reemplazando el elemento con la diferencia del elemento correspondiente del arreglo B. 
Nota: Si esto no es posible, imprima -1.
Ejemplos: 

Entrada: A[] = {5, 7, 10, 5, 15} B[] = {2, 2, 1, 3, 5} 
Salida: 8 
Explicación: 
Pasos para convertir elementos de Array iguales – 
Índice 0: 5 no es cambiado, Pasos tomados = 0 
Índice 1: 7 – (2 * 1) = 5, Pasos tomados = 1 
Índice 2: 10 – (1 * 5) = 5, Pasos tomados = 5 
Índice 3: 5 no ha cambiado, Pasos tomados = 0 
Índice 4: 15 – (5 * 2) = 5, Pasos tomados = 2 
Por lo tanto, pasos totales requeridos = 0 + 1 + 5 + 0 + 2 = 8

Entrada: A[] = {5, 6}, B[] = {4, 3} 
Salida: -1 
Explicación: 
No es posible hacer que todos los elementos de la array sean iguales. 

Enfoque: La idea es encontrar el valor en el que los elementos de la array pueden converger, este valor definitivamente estará entre 0 y el valor mínimo de la array. A continuación se muestra la ilustración del enfoque: 

• Inicialmente, marque la bandera como Falso, para verificar si la array es convertible o no.
• Ejecute un ciclo while hasta que el mínimo de la array sea mayor que -1. 
  • Iterar sobre los índices de la array, es decir, desde 0 hasta longitud – 1
  • Para cada índice, verifique que si el elemento en ese índice en la array A es mayor que el mínimo de la array, en caso afirmativo, actualice el elemento de la array A[i] como A[i] – B[i].
  • Incremente el número de pasos en 1.
  • Verifique que todos los elementos de la array sean iguales en caso afirmativo, luego marque la bandera como Verdadero y rompa el ciclo while
  • De lo contrario, repita los pasos anteriores para calcular el número total de pasos necesarios.
• Finalmente, verifique si la bandera es Verdadera, si es así, entonces la array es convertible.

Explicación con ejemplo: 
las arrays dadas son: A[] = {5, 7, 10, 5, 15}, B[] = {2, 2, 1, 3, 5} 

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

// C++ implementation to find the
// minimum number of steps to convert
// array by subtracting the corresponding
// element from array B
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the minimum steps
void minimumSteps(int ar1[], int ar2[], int n)
{
     
    // Counter to store the steps
    int ans = 0;
      
    // Flag to check that
    // array is converted
    bool flag = true;
      
    // Loop until the minimum of the
    // array is greater than -1
    while (*min_element(ar1, ar1 + n) > -1)
    {
        int a = *min_element(ar1, ar1 + n);
         
        // Loop to convert the array
        // elements by subtraction
        for(int i = 0; i < n; i++)
        {
            if (ar1[i] != a)
            {
                ar1[i] -= ar2[i];
                ans += 1;
            }
        }
         
        set<int> s1(ar1, ar1 + n);
         
        // If the array is converted
        if (s1.size() == 1)
        {
            flag = false;
            cout << ans << endl;
            break;
        }
    }
     
    if (flag)
    {
        cout << -1 << endl;
    }
}
         
// Driver Code
int main()
{
    int n = 5;
    int ar1[] = { 5, 7, 10, 5, 15 };
    int ar2[] = { 1, 2, 1, 5, 5 };
      
    // Function call
    minimumSteps(ar1, ar2, n);
  
    return 0;
}
 
// This code is contributed by rutvik_56

// Java implementation to find the
// minimum number of steps to convert
// array by subtracting the corresponding
// element from array B
import java.util.*;
class GFG{
  
// Function to find the
// minimum steps
static void minimumSteps(int ar1[],
                         int ar2[],
                         int n)
{
  // Counter to store the steps
  int ans = 0;
 
  // Flag to check that
  // array is converted
  boolean flag = true;
 
  // Loop until the minimum of the
  // array is greater than -1
  while (Arrays.stream(ar1).min().getAsInt() > -1)
  {
    int a = Arrays.stream(ar1).min().getAsInt();
 
    // Loop to convert the array
    // elements by subtraction
    for(int i = 0; i < n; i++)
    {
      if (ar1[i] != a)
      {
        ar1[i] -= ar2[i];
        ans += 1;
      }
    }
 
    HashSet<Integer> s1 = new HashSet<>();
    for(int i = 0; i < n; i++)
    {
      s1.add(ar1[i]);
    }
 
    // If the array is converted
    if (s1.size() == 1)
    {
      flag = false;
      System.out.print(ans + "\n");
      break;
    }
  }
 
  if (flag)
  {
    System.out.print(-1 + "\n");
  }
}
         
// Driver Code
public static void main(String[] args)
{
  int n = 5;
  int ar1[] = {5, 7, 10, 5, 15};
  int ar2[] = {1, 2, 1, 5, 5};
 
  // Function call
  minimumSteps(ar1, ar2, n);
}
}
 
// This code is contributed by Princi Singh

# Python3 implementation to find the
# minimum number of steps to convert
# array by subtracting the corresponding
# element from array B
 
# Function to find the minimum steps
def minimumSteps(ar1, ar2, n):
     
    # Counter to store the steps
    ans = 0
     
    # Flag to check that
    # array is converted
    flag = True
     
    # Loop until the minimum of the
    # array is greater than -1
    while min(ar1)>-1:
        a = min(ar1)
         
        # Loop to convert the array
        # elements by subtraction
        for i in range(n):
            if ar1[i]!= a:
                ar1[i]-= ar2[i]
                ans+= 1
                 
        # If the array is converted
        if len(set(ar1))== 1:
            flag = False
            print(ans)
            break
    if flag:
        print(-1)
 
# Driver Code
if __name__ == "__main__":
    n = 5
    ar1 = [5, 7, 10, 5, 15]
    ar2 = [1, 2, 1, 5, 5]
     
    # Function Call
    minimumSteps(ar1, ar2, n)

// C# implementation to
// find the minimum number
// of steps to convert array
// by subtracting the
// corresponding element from
// array B
using System;
using System.Linq;
using System.Collections.Generic;
class GFG{
  
// Function to find the
// minimum steps
static void minimumSteps(int []ar1,
                         int []ar2,
                         int n)
{
  // Counter to store the steps
  int ans = 0;
 
  // Flag to check that
  // array is converted
  bool flag = true;
 
  // Loop until the minimum of the
  // array is greater than -1
  while (ar1.Min() > -1)
  {
    int a = ar1.Min();
 
    // Loop to convert the array
    // elements by subtraction
    for(int i = 0; i < n; i++)
    {
      if (ar1[i] != a)
      {
        ar1[i] -= ar2[i];
        ans += 1;
      }
    }
 
    HashSet<int> s1 = new HashSet<int>();
     
    for(int i = 0; i < n; i++)
    {
      s1.Add(ar1[i]);
    }
 
    // If the array is converted
    if (s1.Count == 1)
    {
      flag = false;
      Console.Write(ans + "\n");
      break;
    }
  }
 
  if (flag)
  {
    Console.Write(-1 + "\n");
  }
}
         
// Driver Code
public static void Main(String[] args)
{
  int n = 5;
  int []ar1 = {5, 7, 10, 5, 15};
  int []ar2 = {1, 2, 1, 5, 5};
 
  // Function call
  minimumSteps(ar1, ar2, n);
}
}
 
// This code is contributed by 29AjayKumar

8

Análisis de rendimiento: 

• Complejidad de tiempo: O(N ² logN) Como en el enfoque anterior, hay dos bucles para convertir la array. El ciclo externo toma O(N) y el ciclo interno toma O(NlogN) ya que estamos usando set en el ciclo interno.
• Espacio Auxiliar: O(N). Estamos usando un conjunto que ocupa O(N) espacio adicional.