Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Footdab's blog

I need help
By Footdab, history, 3 years ago, In English

The problem: Find the nth number that has it's sum of digits divisible by 10. (n <= 10^15) I can only think of digit DP, but I'm trying to think of a simpler way. If anyone can help me, please do.

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

»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Have you tried to investigate how sumOfDigits(n) % 10 behaves when you iterate n = 1..100 or something like this? You probably can come upon the idea...

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

maybe here is a simple way :

long long findNthNumber(int n) {
    long long num = 0, cnt = 0;
    while (cnt < n) {
        num++;
        if (sumOfDigits(num) % 10 == 0) {
            cnt++;
        }
    }
    return num;
}
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I think it can be done in O(1): If k is the sum of digits of n, then the final answer will be concatenation of n and digit q = (10 — k % 10) % 10

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Another gray trying to solve dp before knowing how to sort array :((

→ Reply