wretar's blog

By wretar, history, 4 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please share the constraints?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        Thanks for the help!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks!! Successfully implemented the idea.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for sharing the blog. This has everything that I need.