Problem

Submissions

Hints & solutions

Discuss

Amicable Pair

Easy

0/40

Average time to solve is 15m

Contributed by

2 upvotes

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
4 8
220 284

Sample Output 1:

False
True

Explanation For Sample Input 1:

In test case 1:
Proper divisors of 4 are 1 and 2 with sum 3!=8. 
Proper divisors of 8 are 1, 2, and 4 with sum 7!=4
Thus they are not amicable pairs.

In test case 2:
Proper divisors of X=220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110.
The sum of these is 284 = Y.

Proper divisors of Y=284 are 1, 2, 4, 71, and 142.
The sum of these is 220 = X.

Thus they are amicable pairs.

Sample Input 2:

3
67095 71145
253 487
280 81

Sample Output 2:

True
False
False

Explanation For Sample Input 2:

67095 & 71145 are amicable pairs while 253 & 487 and 280 and 81 are not amicable numbers.

Hint 1

Hint 2

Try to find all proper divisor using brute force.

Approaches (2)

Approach 1

Approach 2

Brute Force

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’.

Time Complexity

O(X + Y), where X and Y are the numbers described in the problem

We will be traversing all the numbers between 1 to X - 1 and from 1 to Y - 1, hence the complexity.

Space Complexity

O(1)

No additional memory will be used except for the reserved stack memory.

(100% EXP penalty)

Amicable Pair

Console