aditya123garg's blog

HackWithInfy Round2 (Doubt)
By aditya123garg, history, 5 years ago, In English

Hey Guys, there was a question in Round 2 of the HackWithInfy Contest which I feel is quite nice and I wasn't able to think of any possible solution to it. So the question goes like that:-

We have defined a function f(x) = sum of all the digits of x. Now,

0 <= i <= N

0 <= j <= N

We have to count how many pairs are there which satisfy the condition that f(i) + f(j) is a prime.

Constraints:- 0 <= N <= 10^50

Example:-

1) N = 2

pairs = 2

2) N = 3

pairs = 4

Can anyone suggest some possible method to solve this question??

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by aditya123garg (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Read this blog you might get some help Digit Dp

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

    Hey, Thnks for replying. I knew about digit dp but couldn't think of the possible recurrence. Can you help with that?

    → Reply