Dados dos arreglos A[] y B[] que constan de N enteros, la tarea es minimizar el costo total de incrementar o decrementar los elementos del arreglo en 1 , de modo que para cada i- ésimo elemento, A[i] sea un múltiplo de B[ i] o viceversa.
Ejemplos:
Entrada: A[] = {3, 6, 3}, B[] = {4, 8, 13}
Salida: 4
Explicación:
Incrementar A[0] en 1 (3 + 1 = 4) lo convierte en múltiplo de B[ 0](= 4).
Incrementar A[1] en 2 (6 + 2 = 8) lo convierte en un múltiplo de B[1](= 8).
Decrementar B[2] en 1 (13 – 1 = 12) lo convierte en un múltiplo de A[2](= 3).
Por lo tanto, el costo total = 1 + 2 + 1 = 4.Entrada: A[] = {13, 2, 31, 7}, B[] = {6, 8, 11, 3}
Salida: 4
Enfoque: El problema dado se puede resolver con avidez . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cost , para almacenar el costo mínimo requerido.
- Atraviese las arrays A[] y B[] simultáneamente y realice los siguientes pasos:
- Caso 1: encuentre el costo de actualizar A[i] para convertirlo en un múltiplo de B[i] , que es el mínimo de (B[i] % A[i]) y (A[i] – B[i] %A[i]) .
- Caso 2: encuentre el costo de actualizar B[i] para convertirlo en un múltiplo de A[i] , que es el mínimo de (A[i] % B[i]) y (B[i] – A[i] %B[i]) .
- Agregue el mínimo de los dos costos anteriores al costo variable de cada elemento del arreglo.
- Después de completar los pasos anteriores, imprima el valor del costo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cost to
// make A[i] multiple of B[i] or
// vice-versa for every array element
int MinimumCost(int A[], int B[],
int N)
{
// Stores the minimum cost
int totalCost = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Case 1: Update A[i]
int mod_A = B[i] % A[i];
int totalCost_A = min(mod_A,
A[i] - mod_A);
// Case 2: Update B[i]
int mod_B = A[i] % B[i];
int totalCost_B = min(mod_B,
B[i] - mod_B);
// Add the minimum of
// the above two cases
totalCost += min(totalCost_A,
totalCost_B);
}
// Return the resultant cost
return totalCost;
}
// Driver Code
int main()
{
int A[] = { 3, 6, 3 };
int B[] = { 4, 8, 13 };
int N = sizeof(A) / sizeof(A[0]);
cout << MinimumCost(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the minimum cost to
// make A[i] multiple of B[i] or
// vice-versa for every array element
static int MinimumCost(int A[], int B[], int N)
{
// Stores the minimum cost
int totalCost = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Case 1: Update A[i]
int mod_A = B[i] % A[i];
int totalCost_A = Math.min(mod_A,
A[i] - mod_A);
// Case 2: Update B[i]
int mod_B = A[i] % B[i];
int totalCost_B = Math.min(mod_B,
B[i] - mod_B);
// Add the minimum of
// the above two cases
totalCost += Math.min(totalCost_A,
totalCost_B);
}
// Return the resultant cost
return totalCost;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 3, 6, 3 };
int B[] = { 4, 8, 13 };
int N = A.length;
System.out.print(MinimumCost(A, B, N));
}
}
// This code is contributed by souravmahato348
Python3
# Python program for the above approach # Function to find the minimum cost to # make A[i] multiple of B[i] or # vice-versa for every array element def MinimumCost(A, B, N): # Stores the minimum cost totalCost = 0 # Traverse the array for i in range(N): # Case 1: Update A[i] mod_A = B[i] % A[i] totalCost_A = min(mod_A, A[i] - mod_A) # Case 2: Update B[i] mod_B = A[i] % B[i] totalCost_B = min(mod_B, B[i] - mod_B) # Add the minimum of # the above two cases totalCost += min(totalCost_A, totalCost_B) # Return the resultant cost return totalCost # Driver Code A = [3, 6, 3] B = [4, 8, 13] N = len(A) print(MinimumCost(A, B, N)) # This code is contributed by shubhamsingh10
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum cost to
// make A[i] multiple of B[i] or
// vice-versa for every array element
static int MinimumCost(int[] A, int[] B, int N)
{
// Stores the minimum cost
int totalCost = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Case 1: Update A[i]
int mod_A = B[i] % A[i];
int totalCost_A = Math.Min(mod_A, A[i] - mod_A);
// Case 2: Update B[i]
int mod_B = A[i] % B[i];
int totalCost_B = Math.Min(mod_B, B[i] - mod_B);
// Add the minimum of
// the above two cases
totalCost += Math.Min(totalCost_A, totalCost_B);
}
// Return the resultant cost
return totalCost;
}
// Driver Code
public static void Main()
{
int[] A = { 3, 6, 3 };
int[] B = { 4, 8, 13 };
int N = A.Length;
Console.Write(MinimumCost(A, B, N));
}
}
// This code is contributed by rishavmahato348
Javascript
<script>
// javascript program for the above approach
// Function to find the minimum cost to
// make A[i] multiple of B[i] or
// vice-versa for every array element
function MinimumCost(A , B , N) {
// Stores the minimum cost
var totalCost = 0;
// Traverse the array
for (i = 0; i < N; i++) {
// Case 1: Update A[i]
var mod_A = B[i] % A[i];
var totalCost_A = Math.min(mod_A, A[i] - mod_A);
// Case 2: Update B[i]
var mod_B = A[i] % B[i];
var totalCost_B = Math.min(mod_B, B[i] - mod_B);
// Add the minimum of
// the above two cases
totalCost += Math.min(totalCost_A, totalCost_B);
}
// Return the resultant cost
return totalCost;
}
// Driver Code
var A = [ 3, 6, 3 ];
var B = [ 4, 8, 13 ];
var N = A.length;
document.write(MinimumCost(A, B, N));
// This code contributed by aashish1995
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA