[LintCode] Amicable Pair

2018-01-13 11:15:56来源:segmentfault作者:linspiration人点击

分享
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<List<Integer>> amicablePair(int k) {
// loop through 1 to k, do calculation, save amicable pairs
List<List<Integer>> 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<Integer> 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;
}
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台