Dadas dos arrays A[] y B[], ambas con N elementos. Encuentre el número mínimo de operaciones para hacer que todos los elementos de A sean iguales a la segunda array B. Una operación se compone de:
A[i] = A[i] - B[i], 0 <= i <= n-1
Nota: si no es posible hacer que los elementos de la array sean iguales, imprima -1.
Ejemplos:
Entrada: A[] = {5, 7, 10, 5, 15}, B[] = {2, 2, 1, 3, 5}
Salida: 8
Explicación: Las
siguientes son las operaciones:
1) Elegir el índice 1 -> 5 5 10 5 15
2) Elegir índice 2 -> 5 5 9 5 15
3) Elegir índice 2 -> 5 5 8 5 15
4) Elegir índice 2 -> 5 5 7 5 15
5) Elegir índice 2 -> 5 5 6 5 15
6) Elegir el índice 2 -> 5 5 5 5 15
7) Elegir el índice 4 -> 5 5 5 5 10
8) Elegir el índice 4 -> 5 5 5 5 5
Entrada: A[] = {3, 5, 8, 2}, B[] = {1, 2, 1, 1}
Salida: 12
Acercarse:
- Se puede observar que el valor máximo posible si todos los elementos de A pueden igualarse es el elemento mínimo de A.
- Entonces podemos iterar sobre el valor final x, cuando todos los elementos de A sean iguales. Usando la observación anterior – 0 <= x <= min(A[i]). Para cada x, recorra A y verifique si A[i] puede hacerse igual a x usando B[i] :
A[i] - k*B[i] = x Take mod with B[i] on both sides A[i] %B[i] = x %B[i] -> must be satisfied for A[i] to be converted to x
- Si se cumple la condición, entonces el número de operaciones requeridas para este elemento = (A[i] – x)/B[i]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum operations make all elements
// equal using the second array
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// operations required to make
// all elements of the array equal
int minOperations(int a[], int b[], int n)
{
// Minimum element of A[]
int minA = *min_element(a, a + n);
// Traverse through all final values
for (int x = minA; x >= 0; x--) {
// Variable indicating
// whether all elements
// can be converted to x or not
bool check = 1;
// Total operations
int operations = 0;
// Traverse through
// all array elements
for (int i = 0; i < n; i++) {
if (x % b[i] == a[i] % b[i]) {
operations +=
(a[i] - x) / b[i];
}
// All elements can't
// be converted to x
else {
check = 0;
break;
}
}
if (check)
return operations;
}
return -1;
}
// Driver Code
int main()
{
int N = 5;
int A[N] = { 5, 7, 10, 5, 15 };
int B[N] = { 2, 2, 1, 3, 5 };
cout << minOperations(A, B, N);
return 0;
}
Java
// Java implementation to find the
// minimum operations make all elements
// equal using the second array
import java.util.*;
class GFG{
// Function to find the minimum
// operations required to make
// all elements of the array equal
static int minOperations(int a[], int b[], int n)
{
// Minimum element of A[]
int minA = Arrays.stream(a).min().getAsInt();
// Traverse through all final values
for (int x = minA; x >= 0; x--)
{
// Variable indicating
// whether all elements
// can be converted to x or not
boolean check = true;
// Total operations
int operations = 0;
// Traverse through
// all array elements
for (int i = 0; i < n; i++)
{
if (x % b[i] == a[i] % b[i])
{
operations += (a[i] - x) / b[i];
}
// All elements can't
// be converted to x
else
{
check = false;
break;
}
}
if (check)
return operations;
}
return -1;
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int A[] = { 5, 7, 10, 5, 15 };
int B[] = { 2, 2, 1, 3, 5 };
System.out.print(minOperations(A, B, N));
}
}
// This code is contributed by AbhiThakur
Python3
# Python3 implementation to find the # minimum operations make all elements # equal using the second array # Function to find the minimum # operations required to make # all elements of the array equal def minOperations(a, b, n): # Minimum element of A minA = min(a); # Traverse through all final values for x in range(minA, -1, -1): # Variable indicating # whether all elements # can be converted to x or not check = True; # Total operations operations = 0; # Traverse through # all array elements for i in range(n): if (x % b[i] == a[i] % b[i]): operations += (a[i] - x) / b[i]; # All elements can't # be converted to x else: check = False; break; if (check): return operations; return -1; # Driver Code if __name__ == '__main__': N = 5; A = [ 5, 7, 10, 5, 15 ]; B = [ 2, 2, 1, 3, 5 ]; print(int(minOperations(A, B, N))); # This code is contributed by amal kumar choubey
C#
// C# implementation to find the
// minimum operations make all elements
// equal using the second array
using System;
using System.Linq;
class GFG{
// Function to find the minimum
// operations required to make
// all elements of the array equal
static int minOperations(int []a, int []b, int n)
{
// Minimum element of A[]
int minA = a.Max();
// Traverse through all final values
for(int x = minA; x >= 0; x--)
{
// Variable indicating
// whether all elements
// can be converted to x or not
bool check = true;
// Total operations
int operations = 0;
// Traverse through
// all array elements
for(int i = 0; i < n; i++)
{
if (x % b[i] == a[i] % b[i])
{
operations += (a[i] - x) / b[i];
}
// All elements can't
// be converted to x
else
{
check = false;
break;
}
}
if (check)
return operations;
}
return -1;
}
// Driver Code
public static void Main(string[] args)
{
int N = 5;
int []A = { 5, 7, 10, 5, 15 };
int []B = { 2, 2, 1, 3, 5 };
Console.WriteLine(minOperations(A, B, N));
}
}
// This code is contributed by SoumikMondal
Javascript
<script>
// javascript implementation to find the
// minimum operations make all elements
// equal using the second array
// Function to find the minimum
// operations required to make
// all elements of the array equal
function minOperations(a , b , n)
{
// Minimum element of A
var minA = Math.max.apply(Math,a);;
// Traverse through all final values
for (x = minA; x >= 0; x--) {
// Variable indicating
// whether all elements
// can be converted to x or not
var check = true;
// Total operations
var operations = 0;
// Traverse through
// all array elements
for (i = 0; i < n; i++) {
if (x % b[i] == a[i] % b[i]) {
operations += (a[i] - x) / b[i];
}
// All elements can't
// be converted to x
else {
check = false;
break;
}
}
if (check)
return operations;
}
return -1;
}
// Driver Code
var N = 5;
var A = [ 5, 7, 10, 5, 15 ];
var B = [ 2, 2, 1, 3, 5 ];
document.write(minOperations(A, B, N));
// This code is contributed by Rajput-Ji
</script>
Producción:
8
Complejidad del tiempo: O(N * min(A i ))
Espacio Auxiliar: O(1)