<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:
        
        # brute force approach
        # start x at 0, check if n + x is beautiful, if not increment x by 1 and repeat

        # better approach -> greedily add a value that will make n's rightmost non-zero digit into zero
        # by turning the column into zero, you will effectively cause the sum of the digits to decrease by multiples of ten
        # sum of digits only really decreases when it hits a multiple of ten

        # pseudocode
        # init a res value
        # check if n is beautiful
        # if not, find number that will make rightmost non-zero digit into zero
            # do this by subtracting that digit from 10
        # += that number to res
        # once n is beautiful, return res

        def digitSum(n):
            sum = 0
            while n:
                sum += n % 10
                n //= 10
            return sum

        # best (most optimal) approach
        res = 0
        base = 1  # Start with the least significant digit place
        while digitSum(n) > target:
            # Find the rightmost non-zero digit
            digit = (n // base) % 10
            if digit != 0:
                # Find the smallest number to add to make the rightmost digit zero
                addition = base * (10 - digit)
                n += addition  # Update the number
                res += addition  # Track total additions made
            base *= 10  # Move to the next digit place (i.e., the next significant position)
        return res
37