How To Find A Pair Of Elements Swapping Which Can Make Sum of Two Arrays Same

0
187
Reduce Function To Sum Array In Dataweave 2.0

Several people have taken to the internet to find out ways to solve this unique problem. As we know, finding a pair of elements swapping that can make the sum of two arrays the same is pretty simple, and at the same time, it’s tricky. That being said, there are some ways to fix this problem easily. In other words, you can easily find the solution to the problem if you follow this article thoroughly. Here, we will provide some codes that can help you with finding the integers. 

Let’s say you have two arrays of integers; then finding a pair of values or one value from each array, that you can use to swap to give the two arrays the same sum becomes easy. So, without further ado, it’s time to take a look at this article and find out the solution to this simple problem. 

Finding A Pair of Values That Can Be Swapped And Yet Make The Sum of Two Arrays Same

First of all, you need to have two arrays of integers. Once you have the numbers or values, uou can find a pair of values that yu can swap to give the two arrays the same run. For example:

Input: A[] = {4,1,2,1,1,2}, B[] =

(3,6,3,3)

Output: {1,3}

Sum of elements in A[] = 11

Sum of elements in B[] 15

To get the same sum from both arrays, we can swap the following values: 1 from A[] and 3 from B[]

Input: A[] = {5,7,4,6}, B[] = {1,2,3,8}

Output: 6,2

Method 1: (Native Implementation)

The first method is to iterate through the arrays and check all sorts of pair of values. This way, you have to compare new sums or look for a pair (of values) with that difference. Here are the following codes for this method:

  1. Codes For C++

// CPP code naive solution to find a pair swapping

// which makes sum of arrays sum.

#include <iostream>

using namespace std;

// Function to calculate sum of elements of array

int getSum(int X[], int n)

{

int sum = 0;

for (int i = 0; i < n; i++)

sum += X[i];

return sum;

}

void findSwapValues(int A[], int n, int B[], int m)

{

// Calculation of sums from both arrays

int sum1 = getSum(A, n);

int sum2 = getSum(B, m);

// Look for val1 and val2, such that

// sumA – val1 + val2 = sumB – val2 + val1

int newsum1, newsum2, val1, val2;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

newsum1 = sum1 – A[i] + B[j];

newsum2 = sum2 – B[j] + A[i];

if (newsum1 == newsum2) {

val1 = A[i];

val2 = B[j];

}

}

}

cout << val1 << ” ” << val2;

}

// Driver code

int main()

{

int A[] = { 4, 1, 2, 1, 1, 2 };

int n = sizeof(A) / sizeof(A[0]);

int B[] = { 3, 6, 3, 3 };

int m = sizeof(B) / sizeof(B[0]);

// Call to function

findSwapValues(A, n, B, m);

return 0;

}

  1.  Codes For Java

// Java program to find a pair swapping

// which makes sum of arrays sum

import java.io.*;

class GFG

{

// Function to calculate sum of elements of array

static int getSum(int X[], int n)

{

int sum = 0;

for (int i = 0; i < n; i++)

sum += X[i];

return sum;

}

// Function to prints elements to be swapped

static void findSwapValues(int A[], int n, int B[], int m)

{

// Calculation of sums from both arrays

int sum1 = getSum(A, n);

int sum2 = getSum(B, m);

// Look for val1 and val2, such that

// sumA – val1 + val2 = sumB – val2 + val1

int newsum1, newsum2, val1 = 0, val2 = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

newsum1 = sum1 – A[i] + B[j];

newsum2 = sum2 – B[j] + A[i];

if (newsum1 == newsum2)

{

val1 = A[i];

val2 = B[j];

}

}

}

System.out.println(val1+” “+val2);

}

// driver program

public static void main (String[] args)

{

int A[] = { 4, 1, 2, 1, 1, 2 };

int n = A.length;

int B[] = { 3, 6, 3, 3 };

int m = B.length;

// Call to function

findSwapValues(A, n, B, m);

}

}

The following output:

1,3,

Time Complexity: O(n*m)

Space Complexity: O(1)

Method 2: Other Native Implementation

There’s another way to do this trick. If you are looking for two values a and b, then:

SumA – a + b = sumB – b + a
2a – 2b = SumA – SumB

a-b= (SumA-SumB)/2

So, we are looking for two digits that have specific target difference, i.e, (SumA-SumB)/2

  1. Codes For C++

// CPP code for naive implementation

#include <iostream>

using namespace std;

// Function to calculate sum of elements of array

int getSum(int X[], int n)

{

int sum = 0;

for (int i = 0; i < n; i++)

sum += X[i];

return sum;

}

// Function to calculate : a – b = (sumA – sumB) / 2

int getTarget(int A[], int n, int B[], int m)

{

// Calculation of sums from both arrays

int sum1 = getSum(A, n);

int sum2 = getSum(B, m);

// because that the target must be an integer

if ((sum1 – sum2) % 2 != 0)

return 0;

return ((sum1 – sum2) / 2);

}

void findSwapValues(int A[], int n, int B[], int m)

{

int target = getTarget(A, n, B, m);

if (target == 0)

return;

// Look for val1 and val2, such that

// val1 – val2 = (sumA – sumB) / 2

int val1, val2;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (A[i] – B[j] == target) {

val1 = A[i];

val2 = B[j];

}

}

}

cout << val1 << ” ” << val2;

}

// Driver code

int main()

{

int A[] = { 4, 1, 2, 1, 1, 2 };

int n = sizeof(A) / sizeof(A[0]);

int B[] = { 3, 6, 3, 3 };

int m = sizeof(B) / sizeof(B[0]);

// Call to function

findSwapValues(A, n, B, m);

return 0;

}

  1. Codes For Java

// Java program to find a pair swapping

// which makes sum of arrays sum

import java.io.*;

class GFG

{

// Function to calculate sum of elements of array

static int getSum(int X[], int n)

{

int sum = 0;

for (int i = 0; i < n; i++)

sum += X[i];

return sum;

}

// Function to calculate : a – b = (sumA – sumB) / 2

static int getTarget(int A[], int n, int B[], int m)

{

// Calculation of sums from both arrays

int sum1 = getSum(A, n);

int sum2 = getSum(B, m);

// because that the target must be an integer

if ((sum1 – sum2) % 2 != 0)

return 0;

return ((sum1 – sum2) / 2);

}

// Function to prints elements to be swapped

static void findSwapValues(int A[], int n, int B[], int m)

{

int target = getTarget(A, n, B, m);

if (target == 0)

return;

// Look for val1 and val2, such that

// val1 – val2 = (sumA – sumB) / 2

int val1 = 0, val2 = 0;

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

if (A[i] – B[j] == target)

{

val1 = A[i];

val2 = B[j];

}

}

}

System.out.println(val1+” “+val2);

}

// driver program

public static void main (String[] args)

{

int A[] = { 4, 1, 2, 1, 1, 2 };

int n = A.length;

int B[] = { 3, 6, 3, 3 };

int m = B.length;

 

// Call to function

findSwapValues(A, n, B, m);

}

} 

Output: 1,3

Time complexity: O(n*m)

Space Complexity O(1)

Method 3- Optimized Solution

For this, you need to sort the arrays. Then, one needs to traverse both arrays at the same time and do the following for every pair:

  1. If the difference is quite small, then make it bigger by moving the “A’” to a bigger value. 
  2. On the other hand, if it’s too big, then make it smaller by moving the B digit to a bigger value. 
  3. If it’s just right, then you need to return this pair. 

Picture

Implementation of this approach is here as follows:

  1. Codes For C++

// CPP code for optimized implementation

#include <bits/stdc++.h>

using namespace std;

// Returns sum of elements in X[]

int getSum(int X[], int n)

{

int sum = 0;

for (int i = 0; i < n; i++)

sum += X[i];

return sum;

}

// Finds value of

// a – b = (sumA – sumB) / 2

int getTarget(int A[], int n, int B[], int m)

{

// Calculation of sums from both arrays

int sum1 = getSum(A, n);

int sum2 = getSum(B, m);

// because that the target must be an integer

if ((sum1 – sum2) % 2 != 0)

return 0;

return ((sum1 – sum2) / 2);

}

// Prints elements to be swapped

void findSwapValues(int A[], int n, int B[], int m)

{

// Call for sorting the arrays

sort(A, A + n);

sort(B, B + m);

// Note that target can be negative

int target = getTarget(A, n, B, m);

// target 0 means, answer is not possible

if (target == 0)

return;

int i = 0, j = 0;

while (i < n && j < m) {

int diff = A[i] – B[j];

if (diff == target) {

cout << A[i] << ” ” << B[j];

return;

}

// Look for a greater value in A[]

else if (diff < target)

i++;

// Look for a greater value in B[]

else

j++;

}

}

// Driver code

int main()

{

int A[] = { 4, 1, 2, 1, 1, 2 };

int n = sizeof(A) / sizeof(A[0]);

int B[] = { 1, 6, 3, 3 };

int m = sizeof(B) / sizeof(B[0]);

findSwapValues(A, n, B, m);

return 0;

}

Output: 2 3

Time Complexity: If arrays are sorted: O(n+m)

If arrays aren’t sorted: O(nlog(n)+mlog(m))

Space Complexity: O(1)

Method 4: (Hashing)

This problem can be solved in O(m+n) time and also O(m) auxiliary space. Here are the algorithm steps:

// assume array1 is small i.e. (m < n)

// where m is array1.length and n is array2.length

  1. Find sum1(sum of small array elements) and sum2

  (sum of larger array elements). // time O(m+n)

  1. Make a hashset for small array(here array1).
  2. Calculate diff as (sum1-sum2)/2.
  3. Run a loop for array2

     for (int i equal to 0 to n-1)

       if (hashset contains (array2[i]+diff))

           print array2[i]+diff and array2[i]

           set flag  and break;

  1. If flag is unset then there is no such kind of 

pair.

Another Quick Approach To Solve This Problem

So, apart from the above-mentioned ones, there’s another approach that you can follow. For example, we can also solve this problem in a linear time using Hashing, as we mentioned earlier. Let’s say that the sum of the elements of the first array a[] is s1, and the second array b[] is s2, and now let’s say the pair that needs to be swapped is (p,q) where p belongs to the first array meanwhile q belongs to the second. 

So, we now have the equation: s1-p+q= s2-q+p, i.e. 2q=s2-s1+2p. Considering both 2p and 2q are even integers, the difference between s2 and s1 must also be an integer. Moreover, given any p, the aim should be to find a proper q satisfying the conditions above. Here’s how you can implement the said approach. 

Codes For C++

#include <bits/stdc++.h>

using namespace std;

void findSwapValues(int a[], int m, int b[], int n);

int main()

{

int a[] = { 4, 1, 2, 1, 1, 2 }, b[] = { 1, 6, 3, 3 };

int m, n;

m = sizeof(a) / sizeof(int),

n = sizeof(b) / sizeof(int);

findSwapValues(a, m, b, n);

return 0;

}

void findSwapValues(int a[], int m, int b[], int n)

{

unordered_set<int> x,

y; /* Unordered sets (and unordered maps) are

implemented internally using hash tables; they

support dictionary operations (i.e. search,

insert, delete) in O(1) time on an average. */

unordered_set<int>::iterator p, q;

int s1, s2;

int i;

s1 = 0;

for (i = 0; i < m;

i++) /* Determining sum s1 of the elements of array

a[], and simultaneously inserting the array

elements in the unordered set. */

s1 += a[i], x.insert(a[i]);

s2 = 0;

for (i = 0; i < n; i++)

s2 += b[i], y.insert(b[i]);

if ((s1 – s2) % 2) /* Checking if difference between the

two array sums

is even or not. */

{

printf(“No such values exist.\n”);

return;

}

for (p = x.begin(); p != x.end(); p++) {

q = y.find(

((s2 – s1) + 2 * *p)

/ 2); // Finding q for a given p in O(1) time.

if (q != y.end()) {

printf(“%d %d\n”, *p, *q);

return;

}

}

printf(“No such values exist.\n”);

}

Output: 2 3

So, the Time Complexity of the code mentioned above is O (m+n), where m and n respectively represent the sizes of the two input arrays mentioned earlier, and the space complexity is O(s+t), where s and t represents the number of distinct elements present in the two input arrays as we know already. 

Conclusion

So, that’s how you can find a pair of elements swapping that makes the sum of two arrays the same. It’s pretty easy, and all you need to do is just to follow the above-mentioned codes.

Read Also: How Many Ounces in a Gallon of Water? Gallon Conversions