Project Euler Problem 76 Statement
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?
Solution
The only difference between this problem and Project Euler Problem 31 is the setup. So, out of paralyzing and extreme laziness I am not going repeat all the wisdom already expounded in that problem's document. I will, however, highlight the key difference: Project Euler 31 uses 8 specific coin denominations, whereas this variation replaces the coins with counting numbers.
HackerRank version
HackerRank Project Euler 76 extends the range of N to 2 ≤ N ≤ 1000 and runs 100 test cases. Since the results can grow extremely large, you are required to output the answers modulo 109 + 7.
Python Source Code
target = 100
ways = [1] + [0]*target
for n in range(1, target+1):
for i in range(n, target+1):
ways[i]+= ways[i-n]
print (ways[target]-1) Last Word
- We Subtract 1 from ways[target] because the problem excludes the single combination where target is used by itself (e.g., 100=100). The requirement is the sum of at least 2 positive integers.
- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000041: a(n) = number of partitions of n (the partition numbers).