Dados dos arreglos A[] y B[] de tamaño N , la tarea es encontrar el recuento mínimo de operaciones requeridas para hacer A[i] múltiplos de B[i] incrementando los subarreglos de prefijos en 1 .
Ejemplos:
Entrada: A[ ] = {3, 2, 9}, B[ ] = {5, 7, 4}, N = 3
Salida: 7
Explicación:
Incrementar {A[0]} dos veces modifica A[] a { 5 , 2, 9}
Incrementar todos los elementos del subarreglo {A[0], A[1]} modifica dos veces A[] a { 7, 4, 9}
Incrementar todos los elementos del subarreglo {A[0], A[1 ], A[2]} tres veces modifica A[] a { 10, 7, 12 }
Por lo tanto, el total de operaciones requeridas = 2 + 2 + 3 = 7.Entrada: A[ ] = {3, 4, 5, 2, 5, 5, 9}, B[ ] = {1, 1, 9, 6, 3, 8, 7}, N = 7
Salida: 22
Planteamiento: El problema se puede resolver usando la técnica Greedy . Para minimizar el número de operaciones, la idea es encontrar el elemento mayor o igual más pequeño más cercano de A[i] que sea un múltiplo de B[i] :
- Atraviesa la array el
- la la
- las operacioneslas
- hacia
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 minimum count of operations // required to make A[i] multiple of B[i] by // incrementing prefix subarray int MinimumMoves(int A[], int B[], int N) { // Stores minimum count of operations // required to make A[i] multiple of B[i] // by incrementing prefix subarray int totalOperations = 0; // Stores the carry int carry = 0; // Stores minimum difference of // correspoinding element in // prefix subarray int K = 0; // Traverse the array for (int i = N - 1; i >= 0; i--) { // Stores the closest greater or equal number // to A[i] which is a multiple of B[i] int nearestMultiple = ceil((double)(A[i] + carry) / (double)(B[i])) * B[i]; // Stores minimum difference K = nearestMultiple - (A[i] + carry); // Update totalOperations totalOperations += K; // Update carry carry += K; } return totalOperations; } // Driver Code int main() { // Input arrays A[] and B[] int A[] = { 3, 4, 5, 2, 5, 5, 9 }; int B[] = { 1, 1, 9, 6, 3, 8, 7 }; // Length of arrays int N = sizeof(A) / sizeof(A[0]); cout << MinimumMoves(A, B, N) << endl; return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find minimum count of operations // required to make A[i] multiple of B[i] by // incrementing prefix subarray static int MinimumMoves(int A[], int B[], int N) { // Stores minimum count of operations // required to make A[i] multiple of B[i] // by incrementing prefix subarray int totalOperations = 0; // Stores the carry int carry = 0; // Stores minimum difference of // correspoinding element in // prefix subarray int K = 0; // Traverse the array for (int i = N - 1; i >= 0; i--) { // Stores the closest greater or equal number // to A[i] which is a multiple of B[i] int nearestMultiple = (int) (Math.ceil((double)(A[i] + carry) / (double)(B[i])) * B[i]); // Stores minimum difference K = nearestMultiple - (A[i] + carry); // Update totalOperations totalOperations += K; // Update carry carry += K; } return totalOperations; } // Driver Code public static void main(String[] args) { // Input arrays A[] and B[] int A[] = { 3, 4, 5, 2, 5, 5, 9 }; int B[] = { 1, 1, 9, 6, 3, 8, 7 }; // Length of arrays int N = A.length; System.out.print(MinimumMoves(A, B, N) +"\n"); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach from math import ceil,floor # Function to find minimum count of operations # required to make A[i] multiple of B[i] by # incrementing prefix subarray def MinimumMoves(A, B, N): # Stores minimum count of operations # required to make A[i] multiple of B[i] # by incrementing prefix subarray totalOperations = 0 # Stores the carry carry = 0 # Stores minimum difference of # correspoinding element in # prefix subarray K = 0 # Traverse the array for i in range(N - 1, -1, -1): # Stores the closest greater or equal number # to A[i] which is a multiple of B[i] nearestMultiple = ceil((A[i] + carry)/ B[i])* B[i] # Stores minimum difference K = nearestMultiple - (A[i] + carry) # Update totalOperations totalOperations += K # Update carry carry += K return totalOperations # Driver Code if __name__ == '__main__': # Input arrays A[] and B[] A = [3, 4, 5, 2, 5, 5, 9] B = [1, 1, 9, 6, 3, 8, 7] # Length of arrays N = len(A) print (MinimumMoves(A, B, N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach using System; class GFG{ // Function to find minimum count of operations // required to make A[i] multiple of B[i] by // incrementing prefix subarray static int MinimumMoves(int[] A, int[] B, int N) { // Stores minimum count of operations // required to make A[i] multiple of B[i] // by incrementing prefix subarray int totalOperations = 0; // Stores the carry int carry = 0; // Stores minimum difference of // correspoinding element in // prefix subarray int K = 0; // Traverse the array for (int i = N - 1; i >= 0; i--) { // Stores the closest greater or equal number // to A[i] which is a multiple of B[i] int nearestMultiple = (int) (Math.Ceiling((double)(A[i] + carry) / (double)(B[i])) * B[i]); // Stores minimum difference K = nearestMultiple - (A[i] + carry); // Update totalOperations totalOperations += K; // Update carry carry += K; } return totalOperations; } // Driver Code public static void Main(string[] args) { // Input arrays A[] and B[] int[] A = { 3, 4, 5, 2, 5, 5, 9 }; int[] B = { 1, 1, 9, 6, 3, 8, 7 }; // Length of arrays int N = A.Length; Console.Write(MinimumMoves(A, B, N) +"\n"); } } // This code is contributed by sanjoy_62.
Javascript
<script> // javascript program of the above approach // Function to find minimum count of operations // required to make A[i] multiple of B[i] by // incrementing prefix subarray function MinimumMoves(A, B, N) { // Stores minimum count of operations // required to make A[i] multiple of B[i] // by incrementing prefix subarray let totalOperations = 0; // Stores the carry let carry = 0; // Stores minimum difference of // correspoinding element in // prefix subarray let K = 0; // Traverse the array for (let i = N - 1; i >= 0; i--) { // Stores the closest greater or equal number // to A[i] which is a multiple of B[i] let nearestMultiple = (Math.ceil((A[i] + carry) / (B[i])) * B[i]); // Stores minimum difference K = nearestMultiple - (A[i] + carry); // Update totalOperations totalOperations += K; // Update carry carry += K; } return totalOperations; } // Driver Code // Input arrays A[] and B[] let A = [ 3, 4, 5, 2, 5, 5, 9 ]; let B = [ 1, 1, 9, 6, 3, 8, 7 ]; // Length of arrays let N = A.length; document.write(MinimumMoves(A, B, N) + "<br/>"); </script>
22
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA