Minimize replacements with values up to K to make sum of two given arrays equal | C ++ program for the above approach ; Function to find minimum number of replacements required to make the sum of two arrays equal ; Stores the sum of a [ ] ; Stores the sum of b [ ] ; Calculate sum of the array a [ ] ; Calculate sum of the array b [ ] ; Stores the difference between a [ ] and b [ ] ; Left and Right pointer to traverse the array a [ ] ; Left and Right pointer to traverse the array b [ ] ; Stores the count of moves ; Sort the arrays in ascending order ; Iterate while diff != 0 and l1 <= r1 or l2 <= r2 ; If diff is greater than 0 ; If all pointers are valid ; Otherwise , if only pointers of array a [ ] is valid ; Otherwise ; If diff is less than 0 ; If all pointers are valid ; Otherwise , if only pointers of array a [ ] is valid ; Otherwise ; Increment count of res by one ; If diff is 0 , then return res ; Otherwise , return - 1 ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int makeSumEqual ( vector < int > a , vector < int > b , int K , int M , int N ) { int sum1 = 0 ; int sum2 = 0 ; for ( int el : a ) sum1 += el ; for ( int el : b ) sum2 += el ; int diff = sum1 - sum2 ; int l1 = 0 , r1 = M - 1 ; int l2 = 0 , r2 = N - 1 ; int res = 0 ; sort ( a . begin ( ) , a . end ( ) ) ; sort ( b . begin ( ) , b . end ( ) ) ; while ( l1 <= r1 l2 <= r2 ) { if ( diff == 0 ) { break ; } if ( diff > 0 ) { if ( l2 <= r2 && l1 <= r1 ) { if ( K - b [ l2 ] < a [ r1 ] - 1 ) { int sub = min ( a [ r1 ] - 1 , diff ) ; diff -= sub ; a [ r1 ] -= sub ; r1 -- ; } else { int sub = min ( K - b [ l2 ] , diff ) ; diff -= sub ; b [ l2 ] += sub ; l2 ++ ; } } else if ( l1 <= r1 ) { int sub = min ( a [ r1 ] - 1 , diff ) ; diff -= sub ; a [ r1 ] -= sub ; r1 -- ; } else { int sub = min ( K - b [ l2 ] , diff ) ; diff -= sub ; b [ l2 ] += sub ; l2 ++ ; } } else { if ( l1 <= r1 && l2 <= r2 ) { if ( K - a [ l1 ] < b [ r2 ] - 1 ) { int sub = min ( b [ r2 ] - 1 , -1 * diff ) ; diff += sub ; b [ r2 ] -= sub ; r2 -- ; } else { int sub = min ( K - a [ l1 ] , -1 * diff ) ; diff += sub ; a [ l1 ] -= sub ; l1 ++ ; } } else if ( l2 <= r2 ) { int sub = min ( b [ r2 ] - 1 , -1 * diff ) ; diff += sub ; b [ r2 ] -= sub ; r2 -- ; } else { int sub = min ( K - a [ l1 ] , diff ) ; diff += sub ; a [ l1 ] += sub ; l1 ++ ; } } res ++ ; } if ( diff == 0 ) return res ; else return -1 ; } int main ( ) { vector < int > A = { 1 , 4 , 3 } ; vector < int > B = { 6 , 6 , 6 } ; int M = A . size ( ) ; int N = B . size ( ) ; int K = 6 ; cout << makeSumEqual ( A , B , K , M , N ) ; return 0 ; }