Sum Swap

Moderate

0/80

Average time to solve is 35m

8 upvotes

Asked in company

Problem statement

You are given two arrays 'NUMS1' and 'NUMS2' of size 'N' and 'M', respectively. You have to swap an element from the first array with an element from the second array. Your task is to determine if it is possible to make the sum of the elements of both the arrays equal after swapping.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow. 

The first line of each test case contains two space-separated integers, 'N' and 'M, as described in the problem statement.

The second line of each test case contains 'N' space-separated integers denoting the elements of the first array 'NUMS1'.

The third line of each test case contains 'M' space-separated integers denoting the elements of the second array 'NUMS2'.

For more clarity, please refer to the sample inputs.

Output Format:

For each test case, print a single line containing “True” if there are such two elements, else print  “False”.

The output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N, M <= 5000
-10 ^ 9 <= X <= 10 ^ 9

Where 'N' and 'M' denote the size of the arrays and 'X' is the value of elements of the arrays.

Time Limit: 1 sec.

Sample Input 1:

Sample Output 1:

True

Explanation for sample input 1:

In the given example, the sum of the elements of the first array is 15, and the sum of the elements of the second array is 19. If we swap 5 from the first array and 7 from the second array, the sum of the first array will now become 17, and the sum of the second array will now become 17 as well. Since the sums are equal, we can return True.

Sample Input 2:

Sample Output 2:

False

Explanation for sample input 2:

In the given example, we can not find a pair of elements(one from each array) such that after swapping them, we can make the sum of the first array equal to the sum of the second array. Hence, the answer is False.

Hint 1

Hint 2

Think of a brute-force solution to find the sum of both the arrays after swapping each pair of elements.

Approaches (2)

Approach 1

Approach 2

Brute-force

The approach is to find the sum of both the arrays beforehand. For every pair of elements, check if, after swapping, the resultant sum of the first array is equal to the resulting sum of the second array.

Steps:

Create two variables ‘SUM1’ and ‘SUM2’ and initialize both of them to 0.
Run a loop from i=0 to ‘N’ and make SUM1 += NUMS1[i].
Run a loop from j=0 to ‘M’ and make SUM2 += NUMS2[j].
Run a loop from i=0 to ‘N’ and do:
1. Run a loop from j=0 to ‘M’ and do:
  1. If (SUM1 + NUMS2[j] - NUMS1[i] == SUM2 + NUMS1[i] - NUMS2[j]), then return True.
If no such pair exists, return False.

Time Complexity

O(N * M), where ‘N’ is the number of elements in the first array and ‘M’ is the number of elements in the second array.

In the worst case, for every element in the first array, we need to traverse the second array completely. Hence, the time complexity is O(N * M).

Space Complexity

O(1).

We are using constant extra memory.

(100% EXP penalty)

Sum Swap

Console