Java Implementation of Problem 76
View source code here on GitHub!
1/*
2Project Euler Problem 76
3
4I ended up having to do this iteratively, which I'm not super happy with. I feel like there is almost certainly a
5closed-form solution to this, but I was unable to figure it out.
6
7Problem:
8
9It is possible to write five as a sum in exactly six different ways:
10
114 + 1
123 + 2
133 + 1 + 1
142 + 2 + 1
152 + 1 + 1 + 1
161 + 1 + 1 + 1 + 1
17
18How many different ways can one hundred be written as a sum of at least two
19positive integers?
20*/
21package euler;
22
23public class p0076 implements IEuler {
24 @Override
25 public Object answer() {
26 int idx, sum = 100, answer = 0;
27 int[] counts = new int[101];
28 counts[2] = 100;
29 while (counts[100] == 0) {
30 counts[2] += 2;
31 if (sum >= 100) {
32 answer += (100 + counts[2] - sum) / 2;
33 idx = 2;
34 do {
35 counts[idx] = 0;
36 idx++;
37 counts[idx] += idx;
38 sum = 0;
39 for (int i = idx - 1; i < 101; i++)
40 sum += counts[i];
41 } while (sum > 100);
42 }
43 sum = 0;
44 for (int i = 0; i < 101; i++)
45 sum += counts[i];
46 }
47 return answer;
48 }
49}