Minimize increment-decrement operation on adjacent elements to convert Array A to B
Given two arrays A[] and B[] consisting of N positive integers, the task is to find the minimum number of increment and decrements of adjacent array elements of the array A[] required to convert it to the array B[]. If it is not possible, then print â-1â.
Examples:
Input: A[] = {1, 2}, B[] = {2, 1}
Output: 1
Explanation:
Perform the following operations on the array A[]:
- Consider the adjacent pairs (arr[0], arr[1]) and after incrementing and decrementing the pairs modifies the array A[] to {2, 1}.
After the above operation, the array A[] = {2, 1} is equal to B and the minimum number of operation required is 1.
Input: A[] = {1, 0, 0}, B[] = {2, 3, 1}
Output: -1
Approach: The given problem can be solved by using the Greedy Approach. Below are the steps:
- It can be observed that if the sum of the arrays A[] and B[] are not equal, then there is no valid sequence of operations exists. In this case, the answer will be -1.
- Otherwise, traverse the given array A[] and perform the following steps according to the following cases:
- Case where A[i] > B[i]:
- In this case keep a track of the extra values(i.e, A[i] â B[i]) Iterate using a pointer j from [i â 1, 0] and keep adding the extra values to the indices until A[j] < B[j] until the extra values gets exhausted (A[i] â B[i] becomes 0) or the end of the array is reached. Similarly, traverse to the right [i + 1, N â 1] and keep adding the extra values.
- Keep a track of the number of moves in a variable and to transfer 1 from index i to index j, the minimum number of operation need is |i â j|.
- Case where A[i] <= B[i]. In this case, iterate to the next value of i because these indices will be considered while iterating during the above-discussed case.
- Case where A[i] > B[i]:
Below is the implementation of the above approach:
C++
// C++ Program of the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the minimum // number of operations to convert // array A to array B by incrementing // and decrementing adjacent elements int minimumMoves( int A[], int B[], int N) { // Stores the final count int ans = 0; // Stores the sum of array A // and B respectively int sum_A = 0, sum_B = 0; for ( int i = 0; i < N; i++) { sum_A += A[i]; } for ( int i = 0; i < N; i++) { sum_B += B[i]; } // Check if the sums are unequal if (sum_A != sum_B) { return -1; } // Pointer to iterate through array int i = 0; while (i < N) { // Case 1 where A[i] > B[i] if (A[i] > B[i]) { // Stores the extra values // for the current index int temp = A[i] - B[i]; int j = i - 1; // Iterate the array from [i-1, 0] while (j >= 0 && temp > 0) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] int cnt = min(temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * abs (j - i)); } j--; } // Iterate the array in right // direction id A[i]-B[i] > 0 if (temp > 0) { int j = i + 1; // Iterate the array from [i+1, n-1] while (j < N && temp > 0) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] int cnt = min(temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * abs (j - i)); } j++; } } } i++; } // Return Answer return ans; } // Driver Code int main() { int A[] = { 1, 5, 7 }; int B[] = { 13, 0, 0 }; int N = sizeof (A) / sizeof ( int ); // Function Call cout << minimumMoves(A, B, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to calculate the minimum // number of operations to convert // array A to array B by incrementing // and decrementing adjacent elements static int minimumMoves( int A[], int B[], int N) { // Stores the final count int ans = 0 ; // Stores the sum of array A // and B respectively int sum_A = 0 , sum_B = 0 ; for ( int i = 0 ; i < N; i++) { sum_A += A[i]; } for ( int i = 0 ; i < N; i++) { sum_B += B[i]; } // Check if the sums are unequal if (sum_A != sum_B) { return - 1 ; } // Pointer to iterate through array int i = 0 ; while (i < N) { // Case 1 where A[i] > B[i] if (A[i] > B[i]) { // Stores the extra values // for the current index int temp = A[i] - B[i]; int j = i - 1 ; // Iterate the array from [i-1, 0] while (j >= 0 && temp > 0 ) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] int cnt = Math.min(temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * Math.abs(j - i)); } j--; } // Iterate the array in right // direction id A[i]-B[i] > 0 if (temp > 0 ) { j = i + 1 ; // Iterate the array from [i+1, n-1] while (j < N && temp > 0 ) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] int cnt = Math.min( temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * Math.abs(j - i)); } j++; } } } i++; } // Return Answer return ans; } // Driver Code public static void main(String[] args) { int A[] = { 1 , 5 , 7 }; int B[] = { 13 , 0 , 0 }; int N = A.length; // Function Call System.out.println(minimumMoves(A, B, N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python 3 Program of the above approach # Function to calculate the minimum # number of operations to convert # array A to array B by incrementing # and decrementing adjacent elements def minimumMoves(A, B, N): # Stores the final count ans = 0 # Stores the sum of array A # and B respectively sum_A = 0 sum_B = 0 for i in range (N): sum_A + = A[i] for i in range (N): sum_B + = B[i] # Check if the sums are unequal if (sum_A ! = sum_B): return - 1 # Pointer to iterate through array i = 0 while (i < N): # Case 1 where A[i] > B[i] if (A[i] > B[i]): # Stores the extra values # for the current index temp = A[i] - B[i] j = i - 1 # Iterate the array from [i-1, 0] while (j > = 0 and temp > 0 ): if (B[j] > A[j]): # Stores the count of # values being transferred # from A[i] to A[j] cnt = min (temp, (B[j] - A[j])) A[j] + = cnt temp - = cnt # Add operation count ans + = (cnt * abs (j - i)) j - = 1 # Iterate the array in right # direction id A[i]-B[i] > 0 if (temp > 0 ): j = i + 1 # Iterate the array from [i+1, n-1] while (j < N and temp > 0 ): if (B[j] > A[j]): # Stores the count of # values being transferred # from A[i] to A[j] cnt = min (temp, (B[j] - A[j])) A[j] + = cnt temp - = cnt # Add operation count ans + = (cnt * abs (j - i)) j + = 1 i + = 1 # Return Answer return ans # Driver Code if __name__ = = '__main__' : A = [ 1 , 5 , 7 ] B = [ 13 , 0 , 0 ] N = len (A) # Function Call print (minimumMoves(A, B, N)) # This code is contributed by ipg2016107. |
C#
// C# program for the above approach using System; public class GFG { // Function to calculate the minimum // number of operations to convert // array A to array B by incrementing // and decrementing adjacent elements static int minimumMoves( int []A, int []B, int N) { // Stores the final count int ans = 0; // Stores the sum of array A // and B respectively int sum_A = 0, sum_B = 0; for ( int i = 0; i < N; i++) { sum_A += A[i]; } for ( int i = 0; i < N; i++) { sum_B += B[i]; } // Check if the sums are unequal if (sum_A != sum_B) { return -1; } // Pointer to iterate through array int k = 0; while (k < N) { // Case 1 where A[i] > B[i] if (A[k] > B[k]) { // Stores the extra values // for the current index int temp = A[k] - B[k]; int j = k - 1; // Iterate the array from [i-1, 0] while (j >= 0 && temp > 0) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] int cnt = Math.Min(temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * Math.Abs(j - k)); } j--; } // Iterate the array in right // direction id A[i]-B[i] > 0 if (temp > 0) { j = k + 1; // Iterate the array from [i+1, n-1] while (j < N && temp > 0) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] int cnt = Math.Min( temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * Math.Abs(j - k)); } j++; } } } k++; } // Return Answer return ans; } // Driver Code public static void Main( string [] args) { int []A = { 1, 5, 7 }; int []B = { 13, 0, 0 }; int N = A.Length; // Function Call Console.WriteLine(minimumMoves(A, B, N)); } } // This code is contributed by AnkThon |
Javascript
<script> // Javascript Program of the above approach // Function to calculate the minimum // number of operations to convert // array A to array B by incrementing // and decrementing adjacent elements function minimumMoves(A, B, N) { // Stores the final count var ans = 0; var i; // Stores the sum of array A // and B respectively var sum_A = 0, sum_B = 0; for (i = 0; i < N; i++) { sum_A += A[i]; } for (i = 0; i < N; i++) { sum_B += B[i]; } // Check if the sums are unequal if (sum_A != sum_B) { return -1; } // Pointer to iterate through array var i = 0; while (i < N) { // Case 1 where A[i] > B[i] if (A[i] > B[i]) { // Stores the extra values // for the current index var temp = A[i] - B[i]; var j = i - 1; // Iterate the array from [i-1, 0] while (j >= 0 && temp > 0) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] var cnt = Math.min(temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * Math.abs(j - i)); } j--; } // Iterate the array in right // direction id A[i]-B[i] > 0 if (temp > 0) { var j = i + 1; // Iterate the array from [i+1, n-1] while (j < N && temp > 0) { if (B[j] > A[j]) { // Stores the count of // values being transferred // from A[i] to A[j] var cnt = Math.min(temp, (B[j] - A[j])); A[j] += cnt; temp -= cnt; // Add operation count ans += (cnt * Math.abs(j - i)); } j++; } } } i++; } // Return Answer return ans; } // Driver Code var A = [1, 5, 7]; var B = [13, 0, 0]; var N = A.length; // Function Call document.write(minimumMoves(A, B, N)); // This code is contributed by SURENDRA_GANGWAR. </script> |
Output:
19
Time Complexity: O(N2)
Auxiliary Space: O(1)