First, we fix a target digit sum between \(1\) and \(9 \cdot \lceil \log_{10} N+1 \rceil\), call it \(s\). Then use a technique known as “digit DP”. where \(dp[a][b][c]\) represents the number of integers with:

• the leftmost \(a\) digits decided (the rest are considered \(0\))
• less than \(N\)’s leftmost \(a\) digits (again, the rest considered \(0\)),
• a digit sum of \(b\),
• a remainder of \(c\), modulo \(s\).

You also need to keep track of the state for the integer with leftmost \(a\) digits equal to \(N\), so you could add to each layer the states where the \(a+1\)-st digit is the first difference from \(N\).

The final time complexity is around \(O(b^4 \log^4 N)\), where \(b\) is the digit base (\(10\)). The time limit is fairly generous, but with careful implementation, it can be made to run even under a second.