adityagamer_alt's blog

By adityagamer_alt, history, 6 weeks ago, In English

You are given N. Find number of pairs of integers x, y such that

1 <= x < y <= N and sumOfDigits(x) > sumOfDigits(y)

Constraints:

N <= 10^100 and is given as a string.

Output answer modulo 1e9+7

I don't remember the sign of inequality properly, it might be sumOfDigits(x) < sumOfDigits(y). I read about digit DP to solve this but I cannot find any approach.

How to solve this?

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

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

Any approach would also be appreciated

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

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

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

keep two tight high (one for x, one for y).

dp states would be : index,thigh1,thigh2,sumx,sumy,flag.

sumx represents sum of digits of x and sumy represents sum of digits of y.

flag is a boolean variable which tells whether at the first place of distinction between digits of x and y , digit of x was smaller or not.