Pairs of Amicable Numbers

Given an array of integers, print the number of pairs in the array that form an amicable pair. Two numbers are amicable if the first is equal to the sum of divisors of the second, and if the second number is equal to the sum of divisors of the first.

Examples :

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

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is to traverse each pair and check if they form an amicable pair, if they do we increment the count.

C++

 // A simple C++ program to count  // amicable pairs in an array. #include 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; }

Java

 // 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

 # 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

C#

 // 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



Output :

2
3

An efficient solution is be to keep the numbers stored in a map and for every number we find the sum of its proper divisor and check if that’s also present in the array. If it is present, we can check if they form an amicable pair or not.

Thus, the complexity would be considerably reduced. Below is the C++ program for the same.

 // Efficient C++ program to count  // Amicable pairs in an array. #include 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 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; }

Output :

2
3

tags:

Arrays Hash Arrays Hash