### wretar's blog

By wretar, history, 4 weeks ago, ,

Find the number of ways a number can be expressed as a sum of primes?

Test Case: Number 7 can be wrtten as 2+2+3, 2+3+2, 2+5, 3+2+2, 5+2 in 5 ways.

This is last year's Nutanix interview question which I came across while sitting for campus placements. It's been one year since I saw the question. Still couldn't figure out how to solve the problem. Any help is really appreciated!!

• -2

 » 4 weeks ago, # |   0 Can you please share the constraints?
•  » » 4 weeks ago, # ^ |   0 Sorry I don't remember the actual constraints. Let us assume 1 <= N <= 1000. Since the answer can be very large, let us return answer mod 1000000009. Hope this helps.
•  » » » 4 weeks ago, # ^ | ← Rev. 5 →   0 Sure. It helps. Precompute all primes using a sieve Let $f(i)$ be the number of ways to express $i$. $f(i) = \sum_{p\le i} f(i - p)$ What we are doing is iterating over the last summand of $i$. If the last summand of $i$ is $p$, then, the integer becomes $(i - p)$. f(0) = 1; for(int i = 1; i <= n; i++) { for(int j = 0; j < primes.size() && primes[j] <= i; j++) { f(i) += f(i - primes[j]); f(i) %= MOD; } } 
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for the help!
•  » » » » 4 weeks ago, # ^ |   0 How can we solve the problem if we consider combinations instead of permutations. For example 7 can be written as 2+2+3, 2+5 in 2 ways.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 Then, we need to introduce another dimension into our DP. Let $f(i, j)$ be the number of ways of writing $i$ where the largest prime is the $j$ th prime. There are two options — We have used the $j$ th prime. Then, we need to add $f(i - p_j, j)$ We have not used the $j$ th prime. Then, we need to add $f(i, j - 1)$ $f(i, j) = f(i - p_j, j) + f(i, j - 1)$ P.S. — This is quite tricky for beginners. The main idea behind finding the state and transition of the DP and ensuring we don't overcount is to create a clear bijection between what we are counting and the DP. In this case, there is a bijection between a way of writing $n$ and the largest prime that we have used.
•  » » » » » » 4 weeks ago, # ^ |   0 Thanks!! Successfully implemented the idea.
 » 4 weeks ago, # |   0 This is a very well known problem. It is called Coin Combinations. You just have to find the primes first. They are the coins here. Then just see Coin Combinations 1 & 2 in this editorial: https://codeforces.com/blog/entry/70018
•  » » 4 weeks ago, # ^ |   0 Thanks for sharing the blog. This has everything that I need.