Last Updated: 7 Apr, 2021

Amicable Pair

Easy

Asked in company

Solve now

Problem statement

You are given two integers ‘X’ and ‘Y’. Your task is to find if the given integers are an amicable pair.

A pair of numbers are called Amicable if the sum of the proper divisor of each number is equal to the other number. Print ‘True’ if the numbers form amicable pair otherwise print ‘False’

A positive proper divisor is a positive divisor of a number, excluding itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.

For example:

Let 'X' = 220 and 'Y' = 284 form an amicable pair as the sum of the proper divisor of one is equal to the other.

Input Format:

The first line of the input contains ‘T’ denoting the number of test cases.

In the first line of each test case take two space-separated integers, ‘X’ and ‘Y’

Output Format:

For each test case, print a string denoting whether the pair are amicable or not, 'True' if pair are amicable else 'False'

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 20
0 <= X,Y <=10^5

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach: Here to find all the proper divisors of a number ‘N’, we will check all the numbers between 1 to N - 1 which divide N. Taking their sum we will compare it with the other number and judge whether the pair is amicable.

Algorithm:

We will create two variables ‘XSUM’=0, ’YSUM’=0 which will store the sum of proper divisors of ‘X’ and ‘Y’ respectively.
To find all proper divisors of the number X we will check all the numbers between 1 to X - 1, which divides ‘X’, and adding it to ‘XSUM’.
We will do the same for finding ‘YSUM’.
Now if ‘XSUM’ == ‘Y’ and ‘YSUM’ == ‘X’ , the pair is amicable, and print ‘True’ else print ‘False’.

Solve now

02 Approach

Approach: The approach is similar except the fact that rather than brute-forcing all the numbers between 1 to N to find divisors, we will just search for divisors from 1 to sqrt(N).

If there exists a divisor between 1 to sqrt(N) let say ‘div’, then since ‘div’ divides ‘N’ then there exists some integer ‘N’ / ’div’ which is also the divisor and will always be greater than or equal to sqrt(N) as ‘div’ is less than or equal to sqrt(N).

Except for the part of finding the perfect divisor all other steps are the same as the previous approach.

Algorithm:

We will create two variables ‘XSUM’=0, ’YSUM’=0 which will store the sum of proper divisors of ‘X’ and ‘Y’ respectively.
To find the proper divisors of X, what we do is traverse all the number from ‘i’= 1 to sqrt(X), if an integer in between is a divisor of X { i.e. X % i ==0 } then i is a proper divisor and we will add it to ‘XSUM’.
If ‘i’ is a divisor of ‘X’ then ‘X’/ ‘i’ will also be a divisor of ‘X’ { but ‘X’ / ’i’ will always be greater than or equal to the root(X) }.
We will add ‘X’ / ‘i’ to ‘XSUM’ only when it is not equal to sqrt(X) { because here ‘i’ will also be equal to sqrt(X) } and ‘X’ { because ‘X’ is not a proper divisor of ‘X’ }
We will do the same for finding ‘YSUM’.
Now if ‘XSUM’ == ‘Y’ and ‘YSUM’ == ‘X’ , the pair is amicable, and print ‘True’ else print 'False’.

Solve now