Maximize Array sum by swapping K elements with another array

Find maximum sum of array A, where k swap can be possible between array A and B. Size of array A and B is N.

Examples:

Input : 
N = 5  k = 5
A[5] = 5 6 5 6 6
B[5] = 1 2 5 4 4
Output : 28
Explanation: 
Sort array A in increasing order
Sort array B in decreasing order
Now check if element of B is greater than element of A, 
then assign greater element to array A.
5 5 6 6 6 
1 2 5 4 4  
array A is 5 5 6 6 6
max sum of array A is 28

Input : 
N = 5 k = 3
A[5] = 1 5 3 4 2
B[5] = 10 9 10 10 9
Output : 39
Explanation: 
A = 1 2 3 4 5 
B = 10 10 10 9 9
After k time swap:
array A is 10 10 10 4 5
max sum of array A is 39

Approach:

Array A is sorted in increasing order and array B is sorted in decreasing order.
k time loop is traversed if element B is greater than element A then greater element is assigned to array A.
Sum of array A elements is calculated and displayed.

# Maxsum function to 
# calculate sum of array A
def Maxsum(A, B, N, k):
    
    # sort array A in 
    # increasing order
    A.sort()
    
    
    # sort array B in 
    # decreasing order
    B.sort(reverse = True)
    
    # iterate over k time
    for i in range(0, k):
        
        # if element of array B is 
        # greater than element of array A
        # then assign greater value to array A
        if(A[i] < B[i]):
            A[i] = B[i]
        
    # Max Sum of array A possible 
    print("Max Sum of array A: ",sum(A))
    
# Driver code
if __name__ == "__main__":
    
    # size of array
    N = 5 
    # number of operation 
    k = 3
    
    # array A
    A = [5, 6, 5, 6, 6]
    # array B
    B = [1, 2, 5, 4, 4]
       
    Maxsum(A,B,N,k)

Output:

Max Sum of array A: 28

Time complexity:

Best case: O(n) 
Worst case: O(nlogn), where n is size

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.