-
Notifications
You must be signed in to change notification settings - Fork 0
/
DigitFactorialChains.java
54 lines (43 loc) · 1.39 KB
/
DigitFactorialChains.java
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
package dev;
import java.util.HashMap;
import java.util.Map;
public class DigitFactorialChains {
private static final int[] factorial = new int[10];
static {
factorial[0] = 1;
for (int i = 1; i < 10; i++) {
factorial[i] = factorial[i - 1] * i;
}
}
public static void main(String[] args) {
int limit = 1000000;
int exactChainCount = 0;
for (int i = 1; i < limit; i++) {
if (calculateNonRepeatingChainLength(i) == 60) {
exactChainCount++;
}
}
System.out.println("Number of starting numbers below " + limit + " with exactly 60 non-repeating terms: " + exactChainCount);
}
private static int calculateNonRepeatingChainLength(int start) {
Map<Integer, Integer> seen = new HashMap<>();
int current = start;
int count = 0;
while (!seen.containsKey(current)) {
seen.put(current, count);
count++;
current = factorialDigitSum(current);
}
// We need the total number of unique terms before any repetition
int nonRepeatingLength = count;
return nonRepeatingLength;
}
private static int factorialDigitSum(int number) {
int sum = 0;
while (number > 0) {
sum += factorial[number % 10];
number /= 10;
}
return sum;
}
}