Amicable Pair(lintcode 243)

Description

An amicable pair (m,n) consists of two integers m,n for which the sum of proper divisors (the divisors excluding the number itself) of one number equals the other.

Given an integer k, find all amicable pairs between 1 and k.

Notice:
For each pair, the first number should be smaller than the second one.

Example

Given 300, return [[220, 284]].

Interface

class Solution {
    /*
     * @param n: The number of digits. 
     * @return: All narcissistic numbers with n digits.
     */
    public ArrayList<Integer> getNarcissisticNumbers(int n) {
        // write your code here
    }
};

Solution

public class Solution {
    /**
     * @param k an integer
     * @return all amicable pairs
     */
    public List<List<Integer>> amicablePair(int k) {
        // Write your code here
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        for (int i = 2; i <= k; ++i) {
            int amicable = getSumOfProperDivisors(i);
            if (amicable <= i || amicable > k) {
                continue;
            }
            if (getSumOfProperDivisors(amicable) == i) {
                ArrayList<Integer> result = new ArrayList<Integer>();
                result.add(i);
                result.add(amicable);
                results.add(result);
            }
        }

        return results;
    }

    private int getSumOfProperDivisors(int m) {
        if (m <= 1) {
            return 0;
        }
        int sum = 1;
        if (m == 2) {
            return sum;
        }

        for (int i = 2; i <= Math.sqrt(m); ++i) {
            if (m % i == 0) {
                sum += i + m / i;
            }
        }
        return sum;
    }
}