anmolsainiii23's blog

Why not Recursive?
By anmolsainiii23, history, 14 months ago, In English

Hi I was wondering why can't we use recursive Solution for Coin Piles Solution. This is the Problem

I have tried recursive solution but end up getting TLE and Runtime Error. Can anyone explain whether we can use Recursion or Dynamic Programing. This is my Solution.

This is my Soluion

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

See the constraint on a, b (1e9). It seems yours code taking O(ab) time and memory

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeahh. Ok got it. But the recurrence was correct?

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      apart from (time / space complexity) yours recurrence solution was correct, but generally recursive solution was slower than dp.

      → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You also can solve it as O(1)

      → Reply