OG - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: ro27
Tester: kaori1
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

The origin of an integer x is determined as follows:

  • If x is a single-digit number, it is its own origin.
  • Otherwise, the origin of x equals the origin of the sum of digits of x.

Given N, find the sum of origins of all integers from 1 to N.

EXPLANATION:

The origin of a number is more commonly called its digital root.

It is well-known that the digital root of a number is simply its remainder when it is divided by 9 (except for the remainder 0, where the digital root is 9 instead).
Even if you haven’t seen this before, you’ll likely observe it immediately upon printing the digital roots of the first few numbers; and it’s fairly easy to prove the pattern too, using the fact that 10^x leaves a remainder of 1 when divided by 9 for every x\geq 0.

With this nice pattern in hand, let’s move on to computing the answer.
Let’s fix a root d, and compute the count of integers \leq N for which d is the digital root.

As noted earlier, this is exactly those numbers whose remainder modulo 9 equals d - that is, integers of the form 9k + d for some integer k \geq 0.
Solving for the inequality 9k+d \leq N gives us k \leq \left \lfloor \frac{N-d}{9} \right\rfloor, and each such k is valid; so we have \left \lfloor \frac{N-d}{9} \right\rfloor + 1 such numbers in total (since k starts from 0).

Each such number adds d to the answer, so multiply this count by d; then repeat for every d.
So, the answer is simply

\sum_{d=1}^9 d\times \left(\left\lfloor \frac{N-d}{9} \right\rfloor + 1 \right)

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    ans = 0
    for d in range(1, 10):
        # d, d+9, ..., d+9x
        # d + 9x <= n -> x <= (n-d)/9
        x = (n-d)//9 + 1
        ans += d*x
    print(ans)
1 Like
2

The modulo 9 in the explanation is pretty hard to understand. Can there be a more simpler breakdown of the last computational part? It would be highly appreciable

1 Like