[LintCode] Amicable Pair

Problem
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]].
Tags Enumeration
Solution
public class Solution {
    /*
     * @param k: An integer
     * @return: all amicable pairs
     */
    public List> amicablePair(int k) {
        // loop through 1 to k, do calculation, save amicable pairs
        List> res = new ArrayList<>();
        for (int i = 1; i <= k; i++) {
            int second = calculateSum(i);
            if (second > k) {
                continue;
            } else {
                int first = calculateSum(second);
                if (first == i && first < second) {
                    List pair = new ArrayList<>();
                    pair.add(first);
                    pair.add(second);
                    res.add(pair);
                }
            }
        }
        
        return res;
    }
    
    public int calculateSum(int n) {
        int sum = 0;
        for (int i = 1; i * i < n; i++) {
            if (n % i == 0) {
                sum += (i+n/i);
            }
            if ((i+1)*(i+1) == n) {
                sum += (i+1);
            }
        }
        return sum-n;
    }
}

좋은 웹페이지 즐겨찾기