Leetcode: 2457. Minimum Addition to Make Integer Beautiful

Problem Statement

Understand the problem

Given two integers \(n\) and \(t\), find the smallest \(x\) which sum of digits of \(n + x\) is at most \(t\).

Solution

Best explanation I have so far: Can we derive an invariant based on the smallest possible examples? We construct \(x\) from right to left, by making sure that \(x_0+n_0=x_1+n_1=...=10\). So, we always minimize the difference of \(d(n+x)\) and \(t\) for each number. 

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        c = n
        p = 10
        while sum(map(int, str(c))) > target:
            c = (c // p + 1) * p
            p = p * 10
        return c - n