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:
-
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;
}
-
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
-
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;
}
-
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:
- If the difference is quite small, then make it bigger by moving the “A’” to a bigger value.
- On the other hand, if it’s too big, then make it smaller by moving the B digit to a bigger value.
- If it’s just right, then you need to return this pair.
Picture
Implementation of this approach is here as follows:
-
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
- Find sum1(sum of small array elements) and sum2
(sum of larger array elements). // time O(m+n)
- Make a hashset for small array(here array1).
- Calculate diff as (sum1-sum2)/2.
- 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;
- 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
