Medium 0 solved 0% acceptance

Amicable Pair

List every amicable pair whose two numbers are both at most a limit.

What you'll learn

  • Build a table of proper-divisor sums for every number up to a limit
  • Check a pair condition in both directions
  • Avoid listing a pair twice or listing perfect numbers

Problem

Let s(n) be the sum of the proper divisors of n (its divisors other than n itself). Two different numbers a and b form an amicable pair when s(a) = b and s(b) = a. The smallest pair is 220 and 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 and s(284) = 1 + 2 + 4 + 71 + 142 = 220.

Implement amicable_pair(limit).

Computing s(n) for every n up to limit one at a time is slow. A sieve works better: for every d, add d to each multiple of d above d.

Input

limit: The largest number either member of a pair may have.

Output

Return a list of pairs [a, b] with a < b ≤ limit, sorted by a in ascending order. A pair is included only if both numbers are at most limit. Perfect numbers (where s(n) = n) are not pairs. If there are none, return an empty list.

Constraints

1 ≤ limit ≤ 200,000

Examples

Example 1
Input:
limit = 1500

Expected output:
expected = [
    [220, 284],
    [1184, 1210]
]
Input:
long long limit = 1500;

Expected output:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Input:
long limit = 1500;

Expected output:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Explanation

s(220) = 284 and s(284) = 220, and s(1184) = 1210 and s(1210) = 1184. Both pairs fit under 1500: [[220, 284], [1184, 1210]].

Example 2
Input:
limit = 250

Expected output:
expected = []
Input:
long long limit = 250;

Expected output:
std::vector<std::vector<long long>> expected = {};
Input:
long limit = 250;

Expected output:
long[][] expected = new long[][] {};

Explanation

220 is at most 250, but its partner 284 is not, so no pair fits: [].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

For every d from 1 to limit / 2, add d to the sums of 2d, 3d, 4d, and so on.

Hint 2

For each a, let b be its divisor sum and check that b is in range and that b's divisor sum is a.

Hint 3

Requiring a < b lists each pair once and skips perfect numbers.

Expected complexity

O(limit log limit) time, O(limit) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.