Showing posts with label count. Show all posts
Showing posts with label count. Show all posts

Wednesday, August 18, 2010

Project Euler # 76: ways can one hundred be written as a sum

It is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?


int n = 100;
int[][] a = new int[n + 1][n + 1];
int i, j, k;
for (i = 0; i < a.length; i++) {
a[i][0] = 0;
a[0][i] = 1;
}
for (i = 1; i < a.length; i++) {
a[i][1] = 1;
for (j = 2; j < a[0].length; j++) {
k = i - j;
if (k < 0)
a[i][j] = a[i][j - 1];
else
a[i][j] = a[i][j - 1] + a[k][j];
}
}
i--;
int answer = a[i][i - 1];

Is my blog being read?