Sum Swap

Posted: 5 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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:

 

  1. Create two variables ‘SUM1’ and ‘SUM2’ and initialize both of them to 0.
  2. Run a loop from i=0 to ‘N’ and make  SUM1 += NUMS1[i].
  3. Run a loop from j=0 to ‘M’ and make  SUM2  += NUMS2[j]. 
  4. 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.
  5. If no such pair exists, return False.
Try Problem