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

Subscribe to:
Post Comments (Atom)

FINAL MATRIX TO GIVE ANSWER WHEN (n=10)

ReplyDelete1 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!!