find all amicable numbers


https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_amicable_pair.html
Amicable number(相亲数)定义:
相亲数(Amicable Pair),又称亲和数、友爱数、友好数,指两个正整数中,彼此的全部约数之和(本身除外)与另一方相等。
例如220与284:
220的全部约数(除掉本身)相加是:1+2+4+5+10+11+20+22+44+55+110=284 284的全部约数(除掉本身)相加的和是:1+2+4+71+142=220
相关题目1:给定整数n,找到小于n的所有amicable number的和
相关知识:
  1、比如36 = 2^2 + 3 ^2。那么它有两个2和三个3是它的质因数,它有(2+1)*(2+1)= 9个约数,因为可以选0个2,1个2或者3个2,对于3同理。
  2. 还有一点:如果factorSum表示这个数所有约数的和,那么 b = factorSum(a), c = factorSum(b), 如果c == a 并且 a != b,那么a和b就是相亲对
所以这题的算法是,找到所有小于根号n的prime number。
对于所有小于n的整数:
  res = 0;
  sum = factorSum(i);
  if(factorSum(sum) == i && i != sum) {
    res += sum;
  }
本道题目:给定整数n,求出所有小于n的相亲数
思路:
求出从1-n所有数的factorSum
for(int i = 2; i <= n / 2; i++) {
    for(int j = i * 2; j <= n; j += i) {
        factorSum[j] += i;
    }
}
道理是,比如n = 20 i = 2,那么4,6,8,10,...,20位置上的sum都+2
i = 3,那么6,9,12,15,18位置上的都+3
时间复杂度O(nlogn). 外层是O(n)内层是1/2+1/3+...+1/n ~ logn
然后统计
public class AmicableNumber {
    public List<List<Integer>> findAmicablePair(int n) {
        List<List<Integer>> res = new ArrayList<>();
        if(n <= 2) {
            return res;
        }
        int[] factorSum = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            factorSum[i] = 1;
        }
        for(int i = 2; i <= n / 2; i++) {
            for(int j = i * 2; j <= n; j += i) {
                factorSum[j] += i;
            }
        }
        //System.out.println(factorSum[10000] + " " + factorSum[23000] );
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 2; i <= n; i++) {
            if(map.containsKey(i) && factorSum[i] == map.get(i)) {
                ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(factorSum[i], i));
                res.add(list);
            } else {
                map.put(factorSum[i], i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //[[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], 
        //[10744, 10856], [12285, 14595], [17296, 18416], [66928, 66992]]
        AmicableNumber sample = new AmicableNumber();
        System.out.println(sample.findAmicablePair(66992));
    }
}
http://coderchen.blogspot.com/2015/11/find-all-amicable-numbers.html
输入一个正整数,找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff,最后写了时间复杂度O(n^1.5),空间复杂度O(n)的算法。
public List<int[]> findAmicable(int num) {
List<int[]> res = new ArrayList<>();
for (int i = 1; i <= num; i++) {
int factorSum = getFactorSum(i);
if (i < factorSum && factorSum <= num) {
int factorSum2 = getFactorSum(factorSum);
if (i == factorSum2) {
res.add(new int[] { i, factorSum });
}
}
}
return res;
}

private int getFactorSum(int num) {
int res = 1;
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
res += i;
res += num / i;
}
}
return res;
}

public static void main(String args[]) {
Solution s = new Solution();
List<int[]> res = s.findAmicable(3000);
for (int[] arr : res) {
System.out.println(arr[0] + " " + arr[1]);
}
}
https://en.wikipedia.org/wiki/Amicable_numbers
Amicable numbers are two different numbers so related that the sum of the proper divisors of each is equal to the other number. 
The smallest pair of amicable numbers is (220284). They are amicable because the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110, of which the sum is 284; and the proper divisors of 284 are 1, 2, 4, 71 and 142, of which the sum is 220.


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts