78. Hackerrank solution.md

Hackerrank Project Euler #78

Question

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5) = 7.

OOOOO

OOOO O

OOO OO

OOO O O

OO OO O

OO O O O

O O O O O

Given T test cases, for each test case N, how many different ways can N coins be separated into piles? As answer can be large, print % (10^9 + 7)

Constraints:

• 1 <= T <= 100
• 2 <= N <= 60000

Solution

Make sure that modulo operation is performed for each pn. Solution submitted in PyPy3 (100/100).

M = 10**9 + 7

def partition(n):
    if n == 0:
        p[0] = 1
        return 
    pn = 0
    for k in range(1, n + 1):
        gk = k * (3 * k - 1) // 2
        if gk > n: break
        pn += (-1) ** (k - 1) * p[n - gk]
        pn %= M
        
        k *= -1
        gk = k * (3 * k - 1) // 2
        if gk > n: break
        pn += int((-1) ** (k - 1)) * p[n - gk]
        pn %= M
    p[n] = pn

N = []
for _ in range(int(input())):
    N.append(int(input()))

p = {}
for n in range(max(N) + 1):
    partition(n)

for n in N:
    print(p[n])