Maximize equal elements in two Arrays after at most K increments
Given two arrays arr1[] and arr2[] of length N each and an integer K, The task is to maximize the number of equal elements at the same index in arr1[] and arr2[] by incrementing any element of arr2[] but the total increment must be at most K.
Examples:
Input: arr1[] = {4, 5, 6, 7}, arr2[] = {3, 4, 5, 7}, K = 3
Output: 4
Explanation: In arr2[] increment the element at index 0 once to make it 4.
Then increment the element at index 1 once to make it 5.
Then increment the element at index 2 once to make it 6.
Total increments performed = 1 + 1 + 1 = 3.
Now both the array contains elements {4, 5, 6, 7}.Input2: arr1[]={5, 2, 5}, arr2[]={1, 1, 4}, K = 2
Output: 2
Approach: The problem can be solved based on the following idea:
We should perform minimum increment operation in each element to maximize the number of the same elements after at most K increments. To find the minimum increment for each element, we should sort difference between same indexed elementsof the two arrays and perform the increment operations accordingly.
Follow the steps mentioned below to implement the idea:
- Iterate from i = 0 to N-1:
- Calculate the difference between the element of arr2[i] and arr1[i].
- Sort the difference array.
- Iterate from i = 0 to N-1:
- Check if this much difference is possible.
- If possible, decrease the value of K by that much and also make the difference 0.
- The total number of elements having a difference of 0 is the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach. #include <bits/stdc++.h> using namespace std; // Function to maximize elements int maxStrength(vector< int >& arr1, vector< int >& arr2, int k, int n) { // Find out required amount each element // should be incremented for ( int i = 0; i < n; i++) { arr1[i] -= arr2[i]; } // Sort the array of difference sort(arr1.begin(), arr1.end()); // Count variable to count the // maximum equal elements int count = 0; for ( int i = 0; i < n; i++) { // Check if any element is 0 // if yes then update the count by 1 if (arr1[i] == 0) { count++; } else if (arr1[i] <= k and arr1[i]>0) { count++; k -= arr1[i]; } else { break ; } } // Return the maximum count of same elements return count; } // Driver code int main() { int N = 4; vector< int > arr1{ 4, 5, 6, 7 }; vector< int > arr2{ 3, 4, 5, 7 }; int K = 3; // Function call cout << maxStrength(arr1, arr2, K, N); return 0; } |
Java
// Java code to implement the approach. import java.util.*; class GFG { // Function to maximize elements static int maxStrength( int [] arr1, int [] arr2, int k, int n) { // Find out required amount each element // should be incremented for ( int i = 0 ; i < n; i++) { arr1[i] -= arr2[i]; } // Sort the array of difference Arrays.sort(arr1); // Count variable to count the // maximum equal elements int count = 0 ; for ( int i = 0 ; i < n; i++) { // Check if any element is 0 // if yes then update the count by 1 if (arr1[i] == 0 ) { count++; } else if (arr1[i] <= k && arr1[i]> 0 ) { count++; k -= arr1[i]; } else { break ; } } // Return the maximum count of same elements return count; } // Driver code public static void main(String[] args) { int N = 4 ; int [] arr1 = { 4 , 5 , 6 , 7 }; int arr2[] = { 3 , 4 , 5 , 7 }; int K = 3 ; // Function call System.out.print(maxStrength(arr1, arr2, K, N)); } } // This code is contributed by shikhasingrajput |
Python3
# Python code to implement the approach. # Function to maximize elements def maxStrength(arr1, arr2, k, n): # Find out required amount each element # should be incremented for i in range (n): arr1[i] - = arr2[i] # Sort the array of difference arr1.sort() # Count variable to count the # maximum equal elements count = 0 for i in range (n): # Check if any element is 0 # if yes then update the count by 1 if (arr1[i] = = 0 ): count + = 1 elif (arr1[i] < = k and arr1[i]> 0 ): count + = 1 k - = arr1[i] else : break # Return the maximum count of same elements return count N = 4 arr1 = [ 4 , 5 , 6 , 7 ] arr2 = [ 3 , 4 , 5 , 7 ] K = 3 # Function call print (maxStrength(arr1, arr2, K, N)) # This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approach. using System; public class GFG { // Function to maximize elements static int maxStrength( int [] arr1, int [] arr2, int k, int n) { // Find out required amount each element // should be incremented for ( int i = 0; i < n; i++) { arr1[i] -= arr2[i]; } // Sort the array of difference Array.Sort(arr1); // Count variable to count the // maximum equal elements int count = 0; for ( int i = 0; i < n; i++) { // Check if any element is 0 // if yes then update the count by 1 if (arr1[i] == 0) { count++; } else if (arr1[i] <= k && arr1[i]>0) { count++; k -= arr1[i]; } else { break ; } } // Return the maximum count of same elements return count; } // Driver code public static void Main(String[] args) { int N = 4; int [] arr1 = { 4, 5, 6, 7 }; int []arr2 = { 3, 4, 5, 7 }; int K = 3; // Function call Console.Write(maxStrength(arr1, arr2, K, N)); } } // This code contributed by shikhasingrajput |
Javascript
<script> // Javascript code to implement the approach. // Function to maximize elements function maxStrength(arr1,arr2, k, n) { // Find out required amount each element // should be incremented for (let i = 0; i < n; i++) { arr1[i] -= arr2[i]; } // Sort the array of difference arr1.sort( function (a, b){ return a - b}); // Count variable to count the // maximum equal elements let count = 0; for (let i = 0; i < n; i++) { // Check if any element is 0 // if yes then update the count by 1 if (arr1[i] == 0) { count++; } else if (arr1[i] <= k && arr1[i]>0) { count++; k -= arr1[i]; } else { break ; } } // Return the maximum count of same elements return count; } // Driver code let N = 4; let arr1=[ 4, 5, 6, 7 ]; let arr2=[ 3, 4, 5, 7 ]; let K = 3; // Function call document.write(maxStrength(arr1, arr2, K, N)); // This code is contributed by satwik4409. </script> |
4
Time Complexity: O(N * logN)
Auxiliary Space: O(1)
Contact Us