Last active
August 11, 2020 00:42
-
-
Save noel-yap/2a6e5d056fd162d027a459e70a9a6572 to your computer and use it in GitHub Desktop.
Digit factorials: https://projecteuler.net/problem=34
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
private Map<Integer, Integer> factorialMemo = new ConcurrentHashMap<Integer, Integer>(); | |
private int factorial(final int n) { | |
final Integer f = factorialMemo.get(n); | |
if (f != null) { | |
return f; | |
} | |
if (n == 0) { | |
return 1; | |
} else { | |
final int fm = n * factorial(n - 1); | |
factorialMemo.put(n, fm); | |
return fm; | |
} | |
} | |
private List<Integer> digits(final int n) { | |
if (n < 10) { | |
return ImmutableList.of(n); | |
} else { | |
final List<Integer> result = new ArrayList<Integer>(); | |
result.add(n % 10); | |
result.addAll(digits(n / 10)); | |
return result; | |
} | |
} | |
private int sumDigitFactorial(final int n) { | |
final List<Integer> d = digits(n); | |
int sum = 0; | |
for (int i = 0; i < d.size(); ++i) { | |
sum += factorial(d.get(i)); | |
} | |
return sum; | |
} | |
private int sumOfValid() { | |
int sum = 0; | |
// Valid solutions can't be larger than 9! | |
for (int i = 10; i < factorial(9); ++i) { | |
if (sumDigitFactorial(i) == i) { | |
sum += i; | |
} | |
} | |
return sum; | |
} | |
@Test | |
public void eyeballTest() { | |
System.out.println(sumOfValid()); | |
} | |
public static void main(String[] args) { | |
JUnitCore.main("Solution"); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment