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
Recommended: Data Types in C | Set 2
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.