[LintCode] Amicable Pair

mumumu 发布于2019-08-15 13:38 / 1124人阅读

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;
    }
}

GPU云服务器云服务器 Amicable pair LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68222.html

[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论0 收藏0
二叉树遍历小结

摘要：对于任一重合元素，保证所在两个局部遍历有序，保证实现整体遍历有序重合元素所在局部局部全部有序，遍历该元素并出栈局部未全部有序，将未有序局部元素全部入栈。二叉树遍历小结声明文章均为本人技术笔记，转载请注明出处： [1] https://segmentfault.com/u/yzwall [2] blog.csdn.net/j_dark/ 0 二叉树遍历概述二叉树遍历：按照既定序，...

vvpale 2019-08-16 10:37 评论0 收藏0
[LintCode] K-diff Pairs in an Array

Problem Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both nu...

Leck1e 2019-08-15 18:16 评论0 收藏0
[LintCode] Submatrix Sum

摘要：原理是这样的先对矩阵的每个点到左顶点之间的子矩阵求和，存在新矩阵上。注意，代表的是到的子矩阵求和。说明从到行，从到列的子矩阵求和为，即相当于两个平行放置的矩形，若左边的值为，左边与右边之和也是，那么右边的值一定为。 Problem Given an integer matrix, find a submatrix where the sum of numbers is zero. Yo...

TesterHome 2019-08-14 15:22 评论0 收藏0