Given two arrays A and B of size N and an integer K, the task is to find the maximum possible sum of array A by swapping at most K elements with array B.
Examples:
Input: A[] = {2, 3, 4}, B[] = {6, 8, 5}, K = 1
Output: 15
Explanation: Swap A[0] and B[1]. Hence sum = 8 + 3 + 4 = 15.Input: A[] = {9, 7}, B[] = {5, 1}, K = 2
Output: 16
Explanation: Since all the elements of array A are greater than the elements of array B, no swaps are required.
Maximize Array sum by swapping at most K elements with another array using Sorting
The idea is to replace all the smallest elements present in A with the largest elements of B, till the value of A[i] < B[i] and K swaps are not complete.
Follow the steps mentioned below to implement the idea:
- Sort the array A and B in non-decreasing order.
- Traverse array A from the beginning and array B from the end, so that we can swap the minimum element of array A with the maximum element of array B.
- If the element of array A is smaller than that of array B, swap them. Otherwise, break the loop.
- Do this for at most K elements, and break the loop after that.
- Find the sum of the resultant array A.
Below is the implementation of the above approach:
C++
// C++ implementation to find maximum// sum of array A by swapping// at most K elements with array B#include <bits/stdc++.h>using namespace std;// Function to find the maximum sumvoid maximumSum(int a[], int b[], int k, int n){ int i, j; sort(a, a + n); sort(b, b + n); // If element of array a is // smaller than that of // array b, swap them. for (i = 0, j = n - 1; i < k; i++, j--) { if (a[i] < b[j]) swap(a[i], b[j]); else break; } // Find sum of resultant array int sum = 0; for (i = 0; i < n; i++) sum += a[i]; cout << sum << endl;}int main(){ int K = 1; int A[] = { 2, 3, 4 }; int B[] = { 6, 8, 5 }; int N = sizeof(A) / sizeof(A[0]); maximumSum(A, B, K, N); return 0;} |
Java
// Java implementation to find maximum// sum of array A by swapping// at most K elements with array Bimport java.util.*;class GFG{// Function to find the maximum sumstatic void maximumSum(int a[], int b[], int k, int n){ int i, j; Arrays.sort(a); Arrays.sort(b); // If element of array a is // smaller than that of // array b, swap them. for (i = 0, j = n - 1; i < k; i++, j--) { if (a[i] < b[j]) { int temp = a[i]; a[i] = b[j]; b[j] = temp; } else break; } // Find sum of resultant array int sum = 0; for (i = 0; i < n; i++) sum += a[i]; System.out.print(sum +"\n");}// Driver Codepublic static void main(String[] args){ int K = 1; int A[] = { 2, 3, 4 }; int B[] = { 6, 8, 5 }; int N = A.length; maximumSum(A, B, K, N);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation to find maximum# sum of array A by swapping# at most K elements with array B# Function to find the maximum sumdef maximumSum(a, b, k, n): a.sort() b.sort() # If element of array a is # smaller than that of # array b, swap them. i = 0 j = n - 1 while i < k: if (a[i] < b[j]): a[i], b[j] = b[j], a[i] else: break i += 1 j -= 1 # Find sum of resultant array sum = 0 for i in range (n): sum += a[i] print(sum)# Driver codeif __name__ == "__main__": K = 1 A = [ 2, 3, 4 ] B = [ 6, 8, 5 ] N = len(A) maximumSum(A, B, K, N)# This code is contributed by chitranayal |
C#
// C# implementation to find maximum// sum of array A by swapping// at most K elements with array Busing System;class GFG{// Function to find the maximum sumstatic void maximumSum(int []a, int []b, int k, int n){ int i, j; Array.Sort(a); Array.Sort(b); // If element of array a is // smaller than that of // array b, swap them. for (i = 0, j = n - 1; i < k; i++, j--) { if (a[i] < b[j]) { int temp = a[i]; a[i] = b[j]; b[j] = temp; } else break; } // Find sum of resultant array int sum = 0; for (i = 0; i < n; i++) sum += a[i]; Console.Write(sum +"\n");}// Driver Codepublic static void Main(){ int K = 1; int []A = { 2, 3, 4 }; int []B = { 6, 8, 5 }; int N = A.Length; maximumSum(A, B, K, N);}}// This code is contributed by Code_Mech |
Javascript
<script>// JavaScript implementation to find maximum// sum of array A by swapping// at most K elements with array B// Function to find the maximum sumfunction maximumSum(a, b, k, n){ let i, j; a.sort(); b.sort(); // If element of array a is // smaller than that of // array b, swap them. for (i = 0, j = n - 1; i < k; i++, j--) { if (a[i] < b[j]) { let temp = a[i]; a[i] = b[j]; b[j] = temp; } else break; } // Find sum of resultant array let sum = 0; for (i = 0; i < n; i++) sum += a[i]; document.write(sum);} let K = 1; let A = [2, 3, 4 ]; let B = [ 6, 8, 5 ]; let N = A.length; maximumSum(A, B, K, N); // This code is contributed by vaibhavrabadiya117.</script> |
Output
15
Time Complexity: O(N*log(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!
