資訊專欄INFORMATION COLUMN
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.
NoticeFor each pair, the first number should be smaller than the second one.
ExampleGiven 300, return [[220, 284]].
TagsEnumeration
Solutionpublic 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68222.html
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...
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...
摘要：對于任一重合元素，保證所在兩個局部遍歷有序，保證實現(xiàn)整體遍歷有序重合元素所在局部局部全部有序，遍歷該元素并出棧局部未全部有序，將未有序局部元素全部入棧。 二叉樹遍歷小結(jié) 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處： [1] https://segmentfault.com/u/yzwall [2] blog.csdn.net/j_dark/ 0 二叉樹遍歷概述 二叉樹遍歷：按照既定序，...
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...
摘要：原理是這樣的先對矩陣的每個點到左頂點之間的子矩陣求和，存在新矩陣上。注意，代表的是到的子矩陣求和。說明從到行，從到列的子矩陣求和為，即相當于兩個平行放置的矩形，若左邊的值為，左邊與右邊之和也是，那么右邊的值一定為。 Problem Given an integer matrix, find a submatrix where the sum of numbers is zero. Yo...
閱讀 2078·2021-10-12 10:12
閱讀 795·2021-09-24 09:47
閱讀 1195·2021-08-19 11:12
閱讀 3483·2019-08-29 13:06
閱讀 692·2019-08-26 11:43
閱讀 2579·2019-08-23 17:20
閱讀 1156·2019-08-23 16:52
閱讀 2607·2019-08-23 14:27
