Wednesday, February 3, 2016

Amicable Pair

Amicable Pair

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.

Example
Given 300, return [[220, 284]].
Note
For each pair, the first number should be smaller than the second one.


注意List的写法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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>> list = new ArrayList<List<Integer>>();
        
        for (int i = 1; i <= k; i++) {
            int second = sumDivisor(i);
            if (second > k) {
                continue;
            }
            
            int first = sumDivisor(second);
            if(first == i && first < second) {
                ArrayList<Integer> pair = new ArrayList<Integer>();
                pair.add(first);
                pair.add(second);
                
                list.add(pair);
            }
        }
        
        return list;
        
    }
    
    
    //Exceed Time Limit
    /*
    public int sumDivisor(int n) {
        int sum = 0;
        for (int i = 1; i < n; i++) {
            if (n % i == 0) {
                sum += i;
            }
        }
        return sum;
    }
    */
    
    public int sumDivisor(int n) {
        int sum = 1, i;
        for (i = 2; i * i < n; ++i) {
            if (n % i == 0) {
                sum += i + n / i;
            }
        }
        if (i * i == n) {
            sum += i;
        }
        return sum;
    }
    
}
Posted by at