Pares de números amistosos

Dada una array de enteros, imprima el número de pares en la array que forman un par amistoso . Dos números son amigos si el primero es igual a la suma de los divisores del segundo y si el segundo número es igual a la suma de los divisores del primero.

Ejemplos: 

Input  : arr[] = {220, 284, 1184, 1210, 2, 5}
Output : 2
Explanation : (220, 284) and (1184, 1210) 
              form amicable pair

Input  : arr[] = {2620, 2924, 5020, 5564, 6232, 6368}
Output : 3
Explanation : (2620, 2924), (5020, 5564) and (6232, 6368)
              forms amicable pair

Una solución simple es recorrer cada par y verificar si forman un par amigable, si lo hacen, incrementamos el conteo. 

Implementación:

// A simple C++ program to count
// amicable pairs in an array.
#include <bits/stdc++.h>
using namespace std;
 
// Calculate the sum
// of proper divisors
int sumOfDiv(int x)
{
    // 1 is a proper divisor
    int sum = 1;
    for (int i = 2; i <= sqrt(x); i++)
    {
        if (x % i == 0)
        {
            sum += i;
 
            // To handle perfect squares
            if (x / i != i)
                sum += x / i;
        }
    }
    return sum;
}
 
// Check if pair is amicable
bool isAmicable(int a, int b)
{
    return (sumOfDiv(a) == b &&
            sumOfDiv(b) == a);
}
 
// This function prints pair
// of amicable pairs present
// in the input array
int countPairs(int arr[], int n)
{
    int count = 0;
 
    // Iterate through each
    // pair, and find if it
    // an amicable pair
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (isAmicable(arr[i], arr[j]))
                count++;
 
    return count;
}
 
// Driver code
int main()
{
    int arr1[] = { 220, 284, 1184,
                   1210, 2, 5 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << countPairs(arr1, n1)
         << endl;
 
    int arr2[] = { 2620, 2924, 5020,
                   5564, 6232, 6368 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << countPairs(arr2, n2);
    return 0;
}

// A simple Java program to count
// amicable pairs in an array.
import java.io.*;
 
class GFG
{
 
    // Calculate the sum
    // of proper divisors
    static int sumOfDiv(int x)
    {
 
        // 1 is a proper divisor
        int sum = 1;
        for (int i = 2; i <= Math.sqrt(x); i++)
        {
            if (x % i == 0)
            {
                sum += i;
 
                // To handle perfect squares
                if (x / i != i)
                    sum += x / i;
            }
        }
 
        return sum;
    }
 
    // Check if pair is amicable
    static boolean isAmicable(int a, int b)
    {
        return (sumOfDiv(a) == b &&
                sumOfDiv(b) == a);
    }
 
    // This function prints pair
    //  of amicable pairs present
    // in the input array
    static int countPairs(int arr[], int n)
    {
        int count = 0;
 
        // Iterate through each pair,
        // and find if it an amicable pair
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (isAmicable(arr[i], arr[j]))
                    count++;
 
        return count;
    }
 
    // Driver code
    public static void main(String args[])
    {
 
        int arr1[] = { 220, 284, 1184,
                       1210, 2, 5 };
        int n1 = arr1.length;
 
        System.out.println(countPairs(arr1, n1));
 
        int arr2[] = { 2620, 2924, 5020,
                       5564, 6232, 6368 };
        int n2 = arr2.length;
 
        System.out.println(countPairs(arr2, n2));
    }
}
 
// This code is contributed by Anshika Goyal.

# Python3 program to count
# amicable pairs in an array
 
# Calculate the sum
# of proper divisors
def sumOfDiv(x):
    sum = 1
    for i in range(2, x):
        if x % i == 0:
            sum += i
    return sum
 
# Check if pair is amicable
def isAmicable(a, b):
    if sumOfDiv(a) == b and sumOfDiv(b) == a:
        return True
    else:
        return False
 
# This function prints pair
# of amicable pairs present
# in the input array
def countPairs(arr, n):
    count = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            if isAmicable(arr[i], arr[j]):
                count = count + 1
    return count
 
# Driver Code
arr1 = [220, 284, 1184,
        1210, 2, 5]
n1 = len(arr1)
print(countPairs(arr1, n1))
 
arr2 = [2620, 2924, 5020,
        5564, 6232, 6368]
n2 = len(arr2)
print(countPairs(arr2, n2))
 
# This code is contributed
# by Smitha Dinesh Semwal

// A simple C# program to count
// amicable pairs in an array.
using System;
 
class GFG
{
     
    // Calculate the sum
    // of proper divisors
    static int sumOfDiv(int x)
    {
         
        // 1 is a proper divisor
        int sum = 1;
        for (int i = 2; i <= Math.Sqrt(x); i++)
        {
            if (x % i == 0)
            {
                sum += i;
 
                // To handle perfect squares
                if (x / i != i)
                    sum += x / i;
            }
        }
         
        return sum;
    }
 
    // Check if pair is amicable
    static bool isAmicable(int a, int b)
    {
        return (sumOfDiv(a) == b &&
                sumOfDiv(b) == a);
    }
 
    // This function prints pair
    // of amicable pairs present
    // in the input array
    static int countPairs(int []arr, int n)
    {
        int count = 0;
 
        // Iterate through each pair,
        // and find if it an amicable pair
        for (int i = 0; i < n; i++)
         
            for (int j = i + 1; j < n; j++)
                if (isAmicable(arr[i], arr[j]))
                    count++;
 
        return count;
    }
 
    // Driver code
    public static void Main()
    {
 
        int []arr1 = {220, 284, 1184,
                      1210, 2, 5};
        int n1 = arr1.Length;
         
        Console.WriteLine(countPairs(arr1, n1));
 
        int []arr2 = {2620, 2924, 5020,
                      5564, 6232, 6368};
        int n2 = arr2.Length;
 
        Console.WriteLine(countPairs(arr2, n2));
    }
}
 
// This code is contributed by vt_m.

<?php
// A simple PHP program to count
// amicable pairs in an array.
 
// Calculate the sum
// of proper divisors
function sumOfDiv( $x)
{
    // 1 is a proper divisor
    $sum = 1;
    for ( $i = 2; $i <= sqrt($x); $i++)
    {
        if ($x % $i == 0)
        {
            $sum += $i;
 
            // To handle perfect squares
            if ($x / $i != $i)
                $sum += $x / $i;
        }
    }
    return $sum;
}
 
// Check if pair is amicable
function isAmicable( $a, $b)
{
    return (sumOfDiv($a) == $b and
            sumOfDiv($b) == $a);
}
 
// This function prints pair
// of amicable pairs present
// in the input array
function countPairs( $arr, $n)
{
    $count = 0;
 
    // Iterate through each pair,
    // and find if it an amicable pair
    for ( $i = 0; $i < $n; $i++)
        for ( $j = $i + 1; $j < $n; $j++)
            if (isAmicable($arr[$i], $arr[$j]))
                $count++;
 
    return $count;
}
 
// Driver code
$arr1 = array( 220, 284, 1184,
               1210, 2, 5 );
$n1 = count($arr1);
echo countPairs($arr1, $n1),"\n";
 
$arr2 = array( 2620, 2924, 5020,
               5564, 6232, 6368 );
$n2 = count($arr2);
echo countPairs($arr2, $n2);
 
// This code is contributed by anuj_67.
?>

<script>
    // A simple Javascript program to count
    // amicable pairs in an array.
     
    // Calculate the sum
    // of proper divisors
    function sumOfDiv(x)
    {
           
        // 1 is a proper divisor
        let sum = 1;
        for (let i = 2; i <= Math.sqrt(x); i++)
        {
            if (x % i == 0)
            {
                sum += i;
   
                // To handle perfect squares
                if (parseInt(x / i, 10) != i)
                    sum += parseInt(x / i, 10);
            }
        }
           
        return sum;
    }
   
    // Check if pair is amicable
    function isAmicable(a, b)
    {
        return (sumOfDiv(a) == b &&
                sumOfDiv(b) == a);
    }
   
    // This function prints pair
    // of amicable pairs present
    // in the input array
    function countPairs(arr, n)
    {
        let count = 0;
   
        // Iterate through each pair,
        // and find if it an amicable pair
        for (let i = 0; i < n; i++)
           
            for (let j = i + 1; j < n; j++)
                if (isAmicable(arr[i], arr[j]))
                    count++;
   
        return count;
    }
     
    let arr1 = [220, 284, 1184, 1210, 2, 5];
    let n1 = arr1.length;
 
    document.write(countPairs(arr1, n1) + "</br>");
 
    let arr2 = [2620, 2924, 5020, 5564, 6232, 6368];
    let n2 = arr2.length;
 
    document.write(countPairs(arr2, n2));
     
</script>

2
3

Una solución eficiente es mantener los números almacenados en un mapa y para cada número, encontramos la suma de su propio divisor y verificamos si eso también está presente en la array. Si está presente, podemos comprobar si forman una pareja amistosa o no.

Así, la complejidad se reduciría considerablemente. A continuación se muestra el programa C++ para el mismo. 

Implementación:

// Efficient C++ program to count
// Amicable pairs in an array.
#include <bits/stdc++.h>
using namespace std;
 
// Calculate the sum
// of proper divisors
int sumOfDiv(int x)
{
    // 1 is a proper divisor
    int sum = 1;
    for (int i = 2; i <= sqrt(x); i++)
    {
        if (x % i == 0) {
            sum += i;
 
            // To handle perfect squares
            if (x / i != i)
                sum += x / i;
        }
    }
    return sum;
}
 
// Check if pair is amicable
bool isAmicable(int a, int b)
{
    return (sumOfDiv(a) == b &&
            sumOfDiv(b) == a);
}
 
// This function prints count
// of amicable pairs present
// in the input array
int countPairs(int arr[], int n)
{
    // Map to store the numbers
    unordered_set<int> s;
    int count = 0;
    for (int i = 0; i < n; i++)
        s.insert(arr[i]);
 
    // Iterate through each number,
    // and find the sum of proper
    // divisors and check if it's
    // also present in the array
    for (int i = 0; i < n; i++)
    {
        if (s.find(sumOfDiv(arr[i])) != s.end())
        {
            // It's sum of proper divisors
            int sum = sumOfDiv(arr[i]);
            if (isAmicable(arr[i], sum))
                count++;
        }
    }
 
    // As the pairs are counted
    // twice, thus divide by 2
    return count / 2;
}
 
// Driver code
int main()
{
    int arr1[] = { 220, 284, 1184,
                   1210, 2, 5 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << countPairs(arr1, n1)
         << endl;
     
    int arr2[] = { 2620, 2924, 5020,
                   5564, 6232, 6368 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << countPairs(arr2, n2)
         << endl;
    return 0;
}

// Efficient Java program to count
// Amicable pairs in an array.
import java.util.*;
 
class GFG
{
 
// Calculate the sum
// of proper divisors
static int sumOfDiv(int x)
{
    // 1 is a proper divisor
    int sum = 1;
    for (int i = 2; i <= Math.sqrt(x); i++)
    {
        if (x % i == 0)
        {
            sum += i;
 
            // To handle perfect squares
            if (x / i != i)
                sum += x / i;
        }
    }
    return sum;
}
 
// Check if pair is amicable
static boolean isAmicable(int a, int b)
{
    return (sumOfDiv(a) == b &&
            sumOfDiv(b) == a);
}
 
// This function prints count
// of amicable pairs present
// in the input array
static int countPairs(int arr[], int n)
{
    // Map to store the numbers
    HashSet<Integer> s = new HashSet<Integer>();
    int count = 0;
    for (int i = 0; i < n; i++)
        s.add(arr[i]);
 
    // Iterate through each number,
    // and find the sum of proper
    // divisors and check if it's
    // also present in the array
    for (int i = 0; i < n; i++)
    {
        if (s.contains(sumOfDiv(arr[i])))
        {
            // It's sum of proper divisors
            int sum = sumOfDiv(arr[i]);
            if (isAmicable(arr[i], sum))
                count++;
        }
    }
 
    // As the pairs are counted
    // twice, thus divide by 2
    return count / 2;
}
 
// Driver code
public static void main(String[] args)
{
    int arr1[] = { 220, 284, 1184,
                   1210, 2, 5 };
    int n1 = arr1.length;
    System.out.println(countPairs(arr1, n1));
     
    int arr2[] = { 2620, 2924, 5020,
                   5564, 6232, 6368 };
    int n2 = arr2.length;
    System.out.println(countPairs(arr2, n2));
}
}
 
// This code is contributed by PrinciRaj1992

# Efficient Python3 program to count
# Amicable pairs in an array.
import math
 
# Calculating the sum
# of proper divisors
def sumOfDiv(x):
     
    # 1 is a proper divisor
    sum = 1;
    for i in range(2,int(math.sqrt(x))):
        if x % i==0:
            sum += i
             
            # To handle perfect squares
            if i != x/i:
                sum += x/i
    return int(sum);
 
# check if pair is amicable
def isAmicable(a, b):
    return (sumOfDiv(a) == b and
            sumOfDiv(b) == a)
 
# This function prints count
# of amicable pairs present
# in the input array
def countPairs(arr,n):
     
    # Map to store the numbers
    s = set()
    count = 0
    for i in range(n):
        s.add(arr[i])
     
    # Iterate through each number,
    # and find the sum of proper
    # divisors and check if it's
    # also present in the array
    for i in range(n):    
        if sumOfDiv(arr[i]) in s:
             
            # It's sum of proper divisors
            sum = sumOfDiv(arr[i])
            if isAmicable(arr[i], sum):
                count += 1       
     
    # As the pairs are counted
    # twice, thus divide by 2
    return int(count/2);
     
# Driver Code
arr1 = [220, 284, 1184,
        1210, 2, 5]
n1 = len(arr1)
print(countPairs(arr1, n1))
 
arr2 = [2620, 2924, 5020,
        5564, 6232, 6368]
n2 = len(arr2)
print(countPairs(arr2, n2))
 
# This code is contributed
# by Naveen Babbar

// Efficient C# program to count
// Amicable pairs in an array.
using System;
using System.Collections.Generic;
     
class GFG
{
 
// Calculate the sum
// of proper divisors
static int sumOfDiv(int x)
{
    // 1 is a proper divisor
    int sum = 1;
    for (int i = 2; i <= Math.Sqrt(x); i++)
    {
        if (x % i == 0)
        {
            sum += i;
 
            // To handle perfect squares
            if (x / i != i)
                sum += x / i;
        }
    }
    return sum;
}
 
// Check if pair is amicable
static Boolean isAmicable(int a, int b)
{
    return (sumOfDiv(a) == b &&
            sumOfDiv(b) == a);
}
 
// This function prints count
// of amicable pairs present
// in the input array
static int countPairs(int []arr, int n)
{
    // Map to store the numbers
    HashSet<int> s = new HashSet<int>();
    int count = 0;
    for (int i = 0; i < n; i++)
        s.Add(arr[i]);
 
    // Iterate through each number,
    // and find the sum of proper
    // divisors and check if it's
    // also present in the array
    for (int i = 0; i < n; i++)
    {
        if (s.Contains(sumOfDiv(arr[i])))
        {
            // It's sum of proper divisors
            int sum = sumOfDiv(arr[i]);
            if (isAmicable(arr[i], sum))
                count++;
        }
    }
 
    // As the pairs are counted
    // twice, thus divide by 2
    return count / 2;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr1 = { 220, 284, 1184,
                   1210, 2, 5 };
    int n1 = arr1.Length;
    Console.WriteLine(countPairs(arr1, n1));
     
    int []arr2 = { 2620, 2924, 5020,
                   5564, 6232, 6368 };
    int n2 = arr2.Length;
    Console.WriteLine(countPairs(arr2, n2));
}
}
 
// This code is contributed by Princi Singh

<script>
 
//  JavaScript program to count
// Amicable pairs in an array.
 
// Calculate the sum
// of proper divisors
function sumOfDiv(x)
{
    // 1 is a proper divisor
    let sum = 1;
    for (let i = 2; i <= Math.sqrt(x); i++)
    {
        if (x % i == 0)
        {
            sum += i;
  
            // To handle perfect squares
            if (x / i != i)
                sum += x / i;
        }
    }
    return sum;
}
  
// Check if pair is amicable
function isAmicable(a, b)
{
    return (sumOfDiv(a) == b &&
            sumOfDiv(b) == a);
}
  
// This function prints count
// of amicable pairs present
// in the input array
function countPairs(arr, n)
{
    // Map to store the numbers
    let s = new Set();
    let count = 0;
    for (let i = 0; i < n; i++)
        s.add(arr[i]);
  
    // Iterate through each number,
    // and find the sum of proper
    // divisors and check if it's
    // also present in the array
    for (let i = 0; i < n; i++)
    {
        if (s.has(sumOfDiv(arr[i])))
        {
            // It's sum of proper divisors
            let sum = sumOfDiv(arr[i]);
            if (isAmicable(arr[i], sum))
                count++;
        }
    }
  
    // As the pairs are counted
    // twice, thus divide by 2
    return  Math.floor(count / 2);
}
     
    // Driver code    
     
    let arr1 = [ 220, 284, 1184,
                   1210, 2, 5 ];
    let n1 = arr1.length;
    document.write(countPairs(arr1, n1) + "<br/>");
      
    let arr2 = [ 2620, 2924, 5020,
                   5564, 6232, 6368 ];
    let n2 = arr2.length;
    document.write(countPairs(arr2, n2) + "<br/>");
      
</script>

2
3

Ashutosh Kumar contribuye con este artículo . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.