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];

1 comment:

  1. FINAL MATRIX TO GIVE ANSWER WHEN (n=10)
    1 1 1 1 1 1 1 1 1 1 1
    0 1 1 1 1 1 1 1 1 1 1
    0 1 2 2 2 2 2 2 2 2 2
    0 1 2 3 3 3 3 3 3 3 3
    0 1 3 4 5 5 5 5 5 5 5
    0 1 3 5 6 7 7 7 7 7 7
    0 1 4 7 9 10 11 11 11 11 11
    0 1 4 8 11 13 14 15 15 15 15
    0 1 5 10 15 18 20 21 22 22 22
    0 1 5 12 18 23 26 28 29 30 30
    0 1 6 14 23 30 35 38 40 41 42

    answer here = 41

    Happy thinking!!

    ReplyDelete

Is my blog being read?