Vlad and a Sum of Sum of Digits (Codeforces 1926C)
Tags: Implement, dp

Please note that the time limit for this problem is only 0.5 seconds per test.Vladislav wrote the integers from $$$1$$$ to $$$n$$$, inclusive, on the board. Then he replaced each integer with the sum of its digits.What is the sum of the numbers on the board now?For example, if $$$n=12$$$ then initially the numbers on the board are: $$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.$$$$$$ Then after the replacement, the numbers become: $$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3.$$$$$$ The sum of these numbers is $$$1+2+3+4+5+6+7+8+9+1+2+3=51$$$. Thus, for $$$n=12$$$ the answer is $$$51$$$.

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the largest number Vladislav writes.

Output: For each test case, output a single integer — the sum of the numbers at the end of the process.


Sample Inputs:
7
12
1
2
3
1434
2024
200000

Sample Outputs:
51
1
3
6
18465
28170
4600002

Solution (Python):
num = int(input())
arr = []
for i in range(num):
    n = int(input())
    summ = n * (n + 1) // 2
    n += 1
    for i in range(6):
        dec = 10 ** (i + 1)
        k = n // dec
        summ -= 9 * ((2 * (n - dec) - (k - 1) * dec) * k // 2)
    arr.append(summ)
for x in arr:
    print(x)

Solution (Python):
def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    t = int(data[0])
    queries = [int(data[i]) for i in range(1, t + 1)]
    max_n = max(queries)
    sum_of_digits = [0] * (max_n + 1)
    for i in range(1, max_n + 1):
        sum_of_digits[i] = sum_of_digits[i // 10] + i % 10
    cumulative_sums = [0] * (max_n + 1)
    for i in range(1, max_n + 1):
        cumulative_sums[i] = cumulative_sums[i - 1] + sum_of_digits[i]
    results = []
    for n in queries:
        results.append(str(cumulative_sums[n]))
    sys.stdout.write('\n'.join(results) + '\n')
solve()

Solution (Python):
import sys
SINGLE_DIGIT_SUM_TABLE = [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
ALL_DIGIT_SUM_TABLE = [0, 45, 900, 13500, 180000, 2250000]

def get_sum(index: int) -> int:
    if index < 10:
        return SINGLE_DIGIT_SUM_TABLE[index]
    _power = 0
    _base = 1
    while 10 ** (_power + 1) <= index:
        _power += 1
        _base *= 10
    _h_digit = index // _base
    _sum = 0
    _sum += SINGLE_DIGIT_SUM_TABLE[_h_digit - 1] * _base
    _sum += _h_digit * ALL_DIGIT_SUM_TABLE[_power]
    _sum += _h_digit * (index % _base + 1)
    _sum += get_sum(index % _base)
    return _sum
n = int(sys.stdin.readline().strip())
for _ in range(n):
    index = int(sys.stdin.readline().strip())
    print(get_sum(index))