Encuentre un par de intercambio de elementos que haga que la suma de dos arrays sea la misma

Posted on by Rudeus Greyrat

Dadas dos arrays de enteros, encuentre un par de valores (un valor de cada array) que pueda intercambiar para dar a las dos arrays la misma suma.
Ejemplos: 
 

Entrada : A[] = {4, 1, 2, 1, 1, 2}, B[] = (3, 6, 3, 3) 
Salida : {1, 3} 
Suma de elementos en A[] = 11 
Suma de elementos en B[] = 15 
Para obtener la misma suma de ambas arrays, podemos 
intercambiar los siguientes valores: 
1 de A[] y 3 de B[]
Entrada : A[] = {5, 7, 4, 6}, B [] = {1, 2, 3, 8} 
Salida : 6 2

 

Método 1 (Implementación ingenua) : 
iterar a través de las arrays y verificar todos los pares de valores. Compara nuevas sumas o busca un par con esa diferencia. 
 
 

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;
}

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);
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python code naive solution to find a pair swapping
# which makes sum of lists sum.
 
# Function to calculate sum of elements of list
def getSum(X):
    sum=0
    for i in X:
        sum+=i
    return sum
 
# Function to prints elements to be swapped
def findSwapValues(A,B):
    # Calculation if sums from both lists
    sum1=getSum(A)
    sum2=getSum(B)
 
    # Boolean variable used to reduce further iterations
    # after the pair is found
    k=False
 
    # Lool for val1 and val2, such that
    # sumA - val1 + val2 = sumB -val2 + val1
    val1,val2=0,0
    for i in A:
        for j in B:
            newsum1=sum1-i+j
            newsum2=sum2-j+i
             
            if newsum1 ==newsum2:
                val1=i
                val2=j
                # Set to True when pair is found
                k=True
                break
        # If k is True, it means pair is found.
        # So, no further iterations.
        if k==True:
            break
    print (val1,val2)
    return
 
 
# Driver code
A=[4,1,2,1,1,2]
B=[3,6,3,3]
 
# Call to function
findSwapValues(A,B)
 
# code contributed by sachin bisht

C#

// C# program to find a pair swapping
// which makes sum of arrays sum
using System;
 
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];
            }
        }
    }
 
    Console.Write(val1 + " " + val2);
}
 
// Driver Code
public static void Main()
{
    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);
}
}
 
// This code is contributed
// by ChitraNayal

PHP

<?php
// PHP code naive solution to find
// a pair swapping which makes sum
// of arrays sum.
 
// Function to calculate sum of
// elements of array
function getSum($X, $n)
{
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $X[$i];
    return $sum;
}
 
function findSwapValues($A, $n, $B, $m)
{
    // Calculation of sums from both arrays
    $sum1 = getSum($A, $n);
    $sum2 = getSum($B, $m);
 
    // Look for val1 and val2, such that
    // sumA - val1 + val2 = sumB - val2 + val1
    for ($i = 0; $i < $n; $i++)
    {
        for ($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];
            }
        }
    }
 
    echo $val1 . " " . $val2;
}
 
// Driver code
$A = array(4, 1, 2, 1, 1, 2 );
$n = sizeof($A);
$B = array(3, 6, 3, 3 );
$m = sizeof($B);
 
// Call to function
findSwapValues($A, $n, $B, $m);
 
// This code is contributed
// by Akanksha Rai
?>

JavaScript

<script>
// Javascript program to find a pair swapping
// which makes sum of arrays sum
     
    // Function to calculate sum of elements of array
    function  getSum(X,n)
    {
        let sum = 0;
        for (let i = 0; i < n; i++)
            sum += X[i];
        return sum;
    }
     
    // Function to prints elements to be swapped
    function findSwapValues(A,n,B,m)
    {
        // Calculation of sums from both arrays
        let sum1 = getSum(A, n);
        let sum2 = getSum(B, m);
    
        // Look for val1 and val2, such that
        // sumA - val1 + val2 = sumB - val2 + val1
        let newsum1, newsum2, val1 = 0, val2 = 0;
        for (let i = 0; i < n; i++)
        {
            for (let 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];
                }
            }
        }
    
        document.write(val1+" "+val2);
    }
     
    // driver program
    let A=[4, 1, 2, 1, 1, 2];
    let n = A.length;
    let B=[3, 6, 3, 3 ];
    let m = B.length;
    // Call to function
    findSwapValues(A, n, B, m);
     
    //This code is contributed by avanitrachhadiya2155
     
</script>
Producción

1 3

Complejidad de tiempo :- O(n*m)
Complejidad de espacio : O(1)

Método 2 -> Otra implementación Naive 
 

We are looking for two values, a and b, such that: 
sumA - a + b = sumB - b + a
    2a - 2b  = sumA - sumB
      a - b  = (sumA - sumB) / 2

Por lo tanto, buscamos dos valores que tengan una diferencia objetivo específica: (sumA – sumB) / 2 . 
 
 

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;
}

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);
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python Code for naive implementation
 
# Function to calculate sum of elements of list
def getSum(X):
    sum=0
    for i in X:
        sum+=i
    return sum
 
# Function to calculate : a-b = (sumA - sumB) / 2
def getTarget(A,B):
 
    #Calculations of sums from both lists
    sum1=getSum(A)
    sum2=getSum(B)
 
    # Because the target must be an integer
    if( (sum1-sum2)%2!=0):
        return 0
    return (sum1-sum2)//2
 
 
def findSwapValues(A,B):
    target=getTarget(A,B)
    if target==0:
        return
 
    # Boolean variable used to reduce further iterations
    # after the pair is found
    flag=False
 
    # Look for val1 and val2, such that
    # val1 - val2 = (sumA -sumB) /2
    val1,val2=0,0
    for i in A:
        for j in B:
             
            if i-j == target:
                val1=i
                val2=j
                # Set to True when pair is found
                flag=True
                break
        if flag==True:
            break
    print (val1,val2)
    return
 
 
# Driver code
A=[4,1,2,1,1,2]
B=[3,6,3,3]
 
# Call to function
findSwapValues(A,B)
 
# code contributed by sachin bisht

C#

// C# program to find a pair swapping
// which makes sum of arrays sum
using System;
 
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];
                }
            }
        }
        Console.Write(val1+" "+val2);
    }
      
    // Driver code
    public static void Main()
    {
        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);
    }
}
 
/*This code is contributed by 29AjayKumar*/

PHP

<?php
// PHP code for naive implementation
 
// Function to calculate sum
// of elements of array
function getSum($X, $n)
{
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum += $X[$i];
    return $sum;
}
 
// Function to calculate :
// a - b = (sumA - sumB) / 2
function getTarget($A, $n, $B, $m)
{
    // Calculation of sums from
    // both arrays
    $sum1 = getSum($A, $n);
    $sum2 = getSum($B, $m);
 
    // because that the target
    // must be an integer
    if (($sum1 - $sum2) % 2 != 0)
        return 0;
    return (($sum1 - $sum2) / 2);
}
 
function findSwapValues($A, $n, $B, $m)
{
    $target = getTarget($A, $n, $B, $m);
    if ($target == 0)
        return;
 
    // Look for val1 and val2, such that
    // val1 - val2 = (sumA - sumB) / 2
    for ($i = 0; $i < $n; $i++)
    {
        for ($j = 0; $j < $m; $j++)
        {
            if ($A[$i] - $B[$j] == $target)
            {
                $val1 = $A[$i];
                $val2 = $B[$j];
            }
        }
    }
 
    echo $val1 . " " . $val2;
}
 
// Driver code
$A = array(4, 1, 2, 1, 1, 2);
$n = sizeof($A);
$B = array(3, 6, 3, 3);
$m = sizeof($B);
 
// Call to function
findSwapValues($A, $n, $B, $m);
 
// This code is contributed
// by Akanksha Rai
?>

JavaScript

<script>
// Javascript program to find a pair swapping
// which makes sum of arrays sum
 
// Function to calculate sum of elements of array
function getSum(X,n)
{
    let sum = 0;
        for (let i = 0; i < n; i++)
            sum += X[i];
        return sum;
}
 
// Function to calculate : a - b = (sumA - sumB) / 2
function getTarget(A,n,B,m)
{
    // Calculation of sums from both arrays
        let sum1 = getSum(A, n);
        let 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
function findSwapValues(A,n,B,m)
{
    let target = getTarget(A, n, B, m);
        if (target == 0)
            return;
   
        // Look for val1 and val2, such that
        // val1 - val2 = (sumA - sumB) / 2
        let val1 = 0, val2 = 0;
        for (let i = 0; i < n; i++)
        {
            for (let j = 0; j < m; j++)
            {
                if (A[i] - B[j] == target)
                {
                    val1 = A[i];
                    val2 = B[j];
                }
            }
        }
        document.write(val1+" "+val2+"<br>");
}
 
// driver program
let A=[4, 1, 2, 1, 1, 2];
let n = A.length;
let B=[3, 6, 3, 3 ];
let m = B.length;
// Call to function
findSwapValues(A, n, B, m);
 
 
 
// This code is contributed by ab2127
</script>
Producción

1 3

Complejidad de tiempo :- O(n*m)
Complejidad de espacio :- O(1)

Método 3 -> Solución optimizada: – 
 

  • Ordenar las arrays.
  • Atraviese ambas arrays simultáneamente y haga lo siguiente para cada par. 
    1. Si la diferencia es demasiado pequeña, hágala más grande moviendo ‘a’ a un valor más grande.
    2. Si es demasiado grande, hazlo más pequeño moviendo b a un valor mayor.
    3. Si es correcto, devuelva este par.

La imagen de abajo es una ejecución en seco del enfoque anterior:
 

A continuación se muestra la implementación del enfoque anterior:
 

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;
}

Java

// Java code for optimized implementation
import java.io.*;
import java.util.*;
 
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)
    {
        // Call for sorting the arrays
        Arrays.sort(A);
        Arrays.sort(B);
  
        // 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)
            {
                System.out.println(A[i]+" "+B[i]);
                return;
            }
  
            // Look for a greater value in A[]
            else if (diff < target)
                i++;
  
            // Look for a greater value in B[]
            else
                j++;
        }
    }
     
    // 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);
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python code for optimized implementation
 
#Returns sum of elements in list
def getSum(X):
    sum=0
    for i in X:
        sum+=i
    return sum
 
# Finds value of
# a - b = (sumA - sumB) / 2
def getTarget(A,B):
    # Calculations of sumd from both lists
    sum1=getSum(A)
    sum2=getSum(B)
 
    # Because that target must be an integer
    if( (sum1-sum2)%2!=0):
        return 0
    return (sum1-sum2)//2
 
# Prints elements to be swapped
def findSwapValues(A,B):
    # Call for sorting the lists
    A.sort()
    B.sort()
 
    #Note that target can be negative
    target=getTarget(A,B)
 
    # target 0 means, answer is not possible
    if(target==0):
        return
    i,j=0,0
    while(i<len(A) and j<len(B)):
        diff=A[i]-B[j]
        if diff == target:
            print (A[i],B[j])
            return
        # Look for a greater value in list A
        elif diff <target:
            i+=1
        # Look for a greater value in list B
        else:
            j+=1
 
A=[4,1,2,1,1,2]
B=[3,6,3,3]
 
findSwapValues(A,B)
 
#code contributed by sachin bisht

C#

// C# code for optimized implementation
using System;
 
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)
    {
        // Call for sorting the arrays
        Array.Sort(A);
        Array.Sort(B);
 
        // 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)
            {
                Console.WriteLine(A[i]+" "+B[i]);
                return;
            }
 
            // Look for a greater value in A[]
            else if (diff < target)
                i++;
 
            // Look for a greater value in B[]
            else
                j++;
        }
    }
     
    // Driver code
    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);
    }
}
 
// This code has been contributed by 29AjayKumar

JavaScript

<script>
// Javascript code for optimized implementation
 
// Function to calculate sum of elements of array
function getSum(X,n)
{
    let sum = 0;
        for (let i = 0; i < n; i++)
            sum += X[i];
        return sum;
}
 
// Function to calculate : a - b = (sumA - sumB) / 2
function getTarget(A,n,B,m)
{
    // Calculation of sums from both arrays
        let sum1 = getSum(A, n);
        let 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
function findSwapValues(A,n,B,m)
{
    // Call for sorting the arrays
        A.sort(function(a,b){return a-b;});
        B.sort(function(a,b){return a-b;});
           
        // Note that target can be negative
        let target = getTarget(A, n, B, m);
           
        // target 0 means, answer is not possible
        if (target == 0)
            return;
   
        let i = 0, j = 0;
        while (i < n && j < m)
        {
            let diff = A[i] - B[j];
             
            if (diff == target)
            {
                document.write(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 program
let A=[4, 1, 2, 1, 1, 2 ];
let n = A.length;
let B=[3, 6, 3, 3 ];
let m = B.length;
// Call to function
findSwapValues(A, n, B, m);
 
 
// This code is contributed by unknown2108
</script>
Producción

2 3

Complejidad de tiempo: – 
Si las arrays están ordenadas: O (n + m) 
Si las arrays no están ordenadas: O (nlog (n) + mlog (m))

Complejidad espacial: O(1)
 
Método 4 (Hashing) 
Podemos resolver este problema en O(m+n) tiempo y O(m) espacio auxiliar. A continuación se muestran los pasos algorítmicos. 
 

// 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) ans sum2
  (sum of larger array elements). // time O(m+n)
2. Make a hashset for small array(here array1).
3. Calculate diff as (sum1-sum2)/2.
4. 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;
5. If flag is unset then there is no such kind of 
pair.

Gracias a nicky khan por sugerir el método 4.
Este artículo es una contribución de Sakshi Tiwari . Si le gusta GeeksforGeeks (¡sabemos que le gusta!) y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Otro enfoque:

También podemos resolver este problema en tiempo lineal usando hashing . Supongamos que la suma de los elementos del primer arreglo a[] es s1, y del segundo arreglo b[] es s2. Suponga también que un par a intercambiar es (p, q), donde p pertenece a a[] y q pertenece a b[]. Por lo tanto, tenemos la ecuación s1 – p + q = s2 – q + p, es decir, 2q = s2 – s1 + 2p . Dado que tanto 2p como 2q son números enteros pares, la diferencia s2 – s1 también debe ser un número entero par . Entonces, dado cualquier p, nuestro objetivo es encontrar un q apropiado que satisfaga las condiciones anteriores.  

A continuación se muestra una implementación de dicho enfoque:

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");
}
Producción

2 3

La complejidad temporal del código anterior es O(m + n) , donde m y n representan respectivamente los tamaños de las dos arrays de entrada, y la complejidad espacial O(s + t) , donde s y t representan respectivamente el número de elementos distintos presentes en las dos arrays de entrada.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *