CODEWITHSUNDEEP
algorithmdynamic-programming
user3404096
user3404096

Reputation: 19

dynamic programmin algorithm to find amount of numbers with n digits that divisible by 3

Give a dynamic programming solution for the following problem. Given a number n>0, compute the number of natural numbers with n digits that are divisible by 3, and do not contain the digit "1".

Hint: The table will have size n×3

i breaking my head on this for a days cant find a sulotion.

Upvotes: 0

Views: 1019

Answers (1)

IVlad
IVlad

Reputation: 43477

Dynamic programming usually involves a recurrence relation that combines the solutions to smaller subproblems.

For your problem, note that for a number to be divisible by 3, its sum of digits must be divisible by 3. Let:

dp[i, s] = how many numbers with i digits have sum of digits s

We have:

dp[i, s] = dp[i - 1, s] +        <- use digit 0
           dp[i - 1, s - 2] +    <- use digit 2
           dp[i - 1, s - 3] +    <- use digit 3
           ...
           dp[i - 1, s - 9]      <- use digit 9

This can indeed by optimized to an n x 3 table (it's now n x S) by working with the sum modulo 3. That and the bases cases are left as an exercise or at least delayed until you show some work.

Upvotes: 2

Related Questions