Given two arrays A[] and B[] of size N, the task is to find the minimum count of operations required to make A[i] multiples of B[i] by incrementing prefix subarrays by 1.
Examples:
Input: A[ ] = {3, 2, 9}, B[ ] = {5, 7, 4}, N = 3
Output: 7
Explanation:
Incrementing {A[0]} twice modifies A[] to {5, 2, 9}
Incrementing all the elements of subarray {A[0], A[1]} twice modifies A[] to {7, 4, 9}
Incrementing all the elements of the subarray {A[0], A[1], A[2]} thrice modifies A[] to {10, 7, 12}
Therefore, total operations required = 2 + 2 + 3 = 7.Input: A[ ] = {3, 4, 5, 2, 5, 5, 9}, B[ ] = {1, 1, 9, 6, 3, 8, 7}, N = 7
Output: 22
Approach: The problem can be solved using the Greedy technique. In order to minimize the number of operations, the idea is to find the closest smallest greater or equal element of A[i] which is a multiple of B[i]:
- Traverse the array A[] from the end to the beginning.
- Find the minimum difference K, between the nearest multiple of the corresponding element of B[].
- Since K is equal to the number of operations at ith element, thus the value of all elements from 0th index till (i-1)th index will increment by K.
- Now maintain a variable carry which will store the cumulative increment, thus if ith element is incremented K times then add K to the carry.
- Value of carry variable will be used to find the new value of (i-1)th element of A[].
Below is the implementation of the above approach:
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 subarrayint 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 Codeint 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 approachimport java.util.*;class GFG{// Function to find minimum count of operations// required to make A[i] multiple of B[i] by// incrementing prefix subarraystatic 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 Codepublic 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 approachfrom math import ceil,floor# Function to find minimum count of operations# required to make A[i] multiple of B[i] by# incrementing prefix subarraydef 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 Codeif __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 approachusing System;class GFG{// Function to find minimum count of operations// required to make A[i] multiple of B[i] by// incrementing prefix subarraystatic 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 Codepublic 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 subarrayfunction 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> |
Output:
22
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
