Last Updated: 5 Mar, 2021

Sum Swap

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The approach is to use hashing. Mark all the elements of the second array true. For every element of the first array, we know exactly which value will be required to make the resultant sums of arrays equal. If for a particular element in the first array, the corresponding value exists in the second array, return True.

Steps:

Make a boolean hashmap ‘EXISTSINNUM2’.
Run a loop from j=0 to M and make EXISTSINNUM2[NUMS2[j]] = true.
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].
If abs(SUM1 - SUM2) % 2 == 1, then that means the difference between both the sum is odd. So one sum is odd and the other sum is even. As two equal numbers sum to an even value, so there is no way in which we can achieve the equal sum of both the arrays. So, we return False.
Run a loop from i=0 to ‘N’ and do:
1. Let ‘EXPECTED’ = NUMS1[i] + (SUM2 - SUM1) / 2.
2. Check if EXISTSINNUM2[EXPECTED] == true, return True.
If no such pair exists, return False.

Solve now