<p>You are given two positive integers <code>n</code> and <code>target</code>.</p>

<p>An integer is considered <strong>beautiful</strong> if the sum of its digits is less than or equal to <code>target</code>.</p>

<p>Return the <em>minimum <strong>non-negative</strong> integer </em><code>x</code><em> such that </em><code>n + x</code><em> is beautiful</em>. The input will be generated such that it is always possible to make <code>n</code> beautiful.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 16, target = 6
<strong>Output:</strong> 4
<strong>Explanation:</strong> Initially n is 16 and its digit sum is 1 + 6 = 7. After adding 4, n becomes 20 and digit sum becomes 2 + 0 = 2. It can be shown that we can not make n beautiful with adding non-negative integer less than 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 467, target = 6
<strong>Output:</strong> 33
<strong>Explanation:</strong> Initially n is 467 and its digit sum is 4 + 6 + 7 = 17. After adding 33, n becomes 500 and digit sum becomes 5 + 0 + 0 = 5. It can be shown that we can not make n beautiful with adding non-negative integer less than 33.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 1, target = 1
<strong>Output:</strong> 0
<strong>Explanation:</strong> Initially n is 1 and its digit sum is 1, which is already smaller than or equal to target.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>12</sup></code></li>
	<li><code>1 &lt;= target &lt;= 150</code></li>
	<li>The input will be generated such that it is always possible to make <code>n</code> beautiful.</li>
</ul>

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        cur = []
        '''
        num = n
        while num:
            cur.append(num % 10)
            num //= 10
        cur = cur[::-1]
        '''
        cur = list(map(int, str(n)))
        r = len(cur) - 1
        while sum(cur) > target:
            cur[r] = 0
            r -= 1
            if cur[r] == 9:
                while cur[r] == 9:
                    cur[r] = 0
                    r -= 1
            if r >= 0:  #这个有点太复杂了，单独进位还要考虑
                cur[r] += 1 
        if r < 0:
            cur = [1] + cur  # 处理类似 999 变为 1000 的情况
        cur = "".join(map(str, cur))  #或者用"".join([str(i) for i in cur]) 也可以，直接用"".join(str(cur))不对，因为list整个相当于是"[1,2,3]" 
        res = int(cur) - n
        
        return res


class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        ans = added = 0
        mask = 10
        while sum([int(c) for c in str(n)]) > target:
            added = mask - n % mask
            if added != mask:
                n += added
                ans += added
            mask *= 10
        return ans
41