# Minimum Addition to Make Integer Beautiful
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-addition-to-make-integer-beautiful)
Canonical: https://scaleengineer.com/dsa/problems/minimum-addition-to-make-integer-beautiful
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
You are given two positive integers `n` and `target`.

An integer is considered **beautiful** if the sum of its digits is less than or equal to `target`.

Return the _minimum **non-negative** integer_ `x` _such that_ `n + x` _is beautiful_. The input will be generated such that it is always possible to make `n` beautiful.

**Example 1:**

**Input:** n = 16, target = 6
**Output:** 4
**Explanation:** 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.

**Example 2:**

**Input:** n = 467, target = 6
**Output:** 33
**Explanation:** 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.

**Example 3:**

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

**Constraints:**

* `1 <= n <= 1012`
* `1 <= target <= 150`
* The input will be generated such that it is always possible to make `n` beautiful.

# Approaches
## Brute Force by Incrementing
This approach is the most straightforward and intuitive way to think about the problem. We are looking for the smallest non-negative integer `x`. We can simply start checking from `x = 0`, `x = 1`, `x = 2`, and so on. For each value of `x`, we compute `n + x` and check if its digit sum is less than or equal to `target`. The first `x` that satisfies this condition is guaranteed to be the minimum, so we can return it immediately.
**Time:** O(x * log(n+x))

Let `x` be the final answer. The main loop runs `x` times. Inside the loop, we calculate the digit sum of `n + x`, which takes `O(log(n+x))` time. In the worst case, `x` can be large (e.g., close to a power of 10), making this approach too slow for the given constraints. · **Space:** O(1)

We only use a few variables to store `x`, the current sum, and intermediate values, regardless of the input size.
**Pros:** Very simple to understand and implement.; It is guaranteed to find the correct minimum `x` because it checks values in increasing order.
**Cons:** The time complexity is dependent on the magnitude of the result `x`, which can be very large.; This approach will result in a 'Time Limit Exceeded' (TLE) error on platforms with stricter time limits for most of the test cases, given the constraints on `n`.
### Explanation
The algorithm begins by initializing `x` to 0. It then enters a loop that will continue until a beautiful number is found. In each iteration, it computes `n + x` and calculates the sum of its digits. A helper function, `getDigitSum`, is used for this purpose. This function repeatedly takes the number modulo 10 to get the last digit and adds it to a sum, then divides the number by 10 to remove the last digit, until the number becomes 0. If the digit sum of `n + x` is within the `target`, the loop terminates and `x` is returned. Otherwise, `x` is incremented, and the process repeats for the next integer.

```java
class Solution {
    private long getDigitSum(long num) {
        long sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public long makeIntegerBeautiful(long n, int target) {
        long x = 0;
        while (true) {
            long currentN = n + x;
            if (getDigitSum(currentN) <= target) {
                return x;
            }
            x++;
        }
    }
}
```
### Algorithm
1. Initialize a variable `x` to `0`. This `x` represents the non-negative integer we are adding to `n`.
2. Start an infinite loop.
3. Inside the loop, calculate the current number `currentN = n + x`.
4. Define a helper function `getDigitSum(num)` that calculates the sum of the digits of a given number `num`.
5. Call `getDigitSum(currentN)` to get the sum of digits for the current number.
6. Check if the calculated sum is less than or equal to `target`.
7. If it is, `currentN` is beautiful. We have found the minimum `x`, so we return `x`.
8. If the sum is greater than `target`, increment `x` by 1 and continue the loop.

## Greedy Approach by Rounding Up
A more efficient approach is to observe how the digit sum changes when we add a number. Adding a small number usually increases the digit sum. To decrease it, we need to cause a carry-over, which turns digits into zeros. The most effective way to do this is to make the rightmost digits of the number zero. This can be achieved by rounding the number up to the next power of 10.

For example, if `n = 467` and `target = 6`, the digit sum is 17. We first round `467` up to the next multiple of 10, which is `470`. The digit sum is now 11, which is still too high. So, we round `470` up to the next multiple of 100, which is `500`. The digit sum is 5, which is less than or equal to the target. The total value added is `500 - 467 = 33`. This greedy strategy of zeroing out digits from right to left gives us the minimum `x`.
**Time:** O((log n)^2)

The number of digits in `n` is approximately `log10(n)`. The main loop runs at most once for each digit place, so it runs `O(log n)` times. Inside the loop, `getDigitSum` also takes `O(log n)` time. Therefore, the total time complexity is `O(log n * log n) = O((log n)^2)`. Given `n <= 10^12`, `log n` is very small (around 12-13), making this approach extremely fast. · **Space:** O(1)

The algorithm uses a constant amount of extra space for variables like `place`, `originalN`, etc.
**Pros:** Highly efficient and fast, easily passing within time limits.; Correctly finds the minimum `x` by making the smallest necessary changes to achieve the goal.; Handles large numbers up to 10^12 effectively.
**Cons:** The logic is slightly more complex than the brute-force approach, requiring a good understanding of place values and the rounding-up strategy.
### Explanation
This greedy algorithm iteratively modifies `n` to make it beautiful. We start by checking if `n` is already beautiful. If not, we begin a process of rounding up. We use a `place` variable, starting at `10`, to represent the position we are trying to zero out. In each step of a loop, we calculate how much we need to add to `n` to make it a multiple of the current `place`. We add this amount and then re-check if the new number is beautiful. If it is, we've found our target number, and the difference between this and the original `n` is our answer `x`. If not, we increase our `place` by a factor of 10 (to `100`, `1000`, etc.) and repeat the rounding-up process. This continues until the digit sum condition is met.

```java
class Solution {
    private long getDigitSum(long num) {
        long sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public long makeIntegerBeautiful(long n, int target) {
        if (getDigitSum(n) <= target) {
            return 0;
        }

        long originalN = n;
        long place = 10;

        while (true) {
            long remainder = n % place;
            // If remainder is 0, n is already a multiple of place.
            // But we still need to round up to reduce the sum, so we add the full 'place'.
            // A simpler way is to just calculate the next multiple.
            n = (n / place + 1) * place;

            if (getDigitSum(n) <= target) {
                return n - originalN;
            }
            
            place *= 10;
        }
    }
}
```
An alternative implementation of the loop body that might be more intuitive:
```java
// Inside the while(true) loop
long remainder = n % place;
if (remainder != 0) { // Only add if not already a multiple
    long toAdd = place - remainder;
    n += toAdd;
}
if (getDigitSum(n) <= target) {
    return n - originalN;
}
place *= 10;
```
However, the first version `n = (n / place + 1) * place;` is more concise and correctly handles all cases, including when `n` is already a multiple of `place` but still needs modification (e.g., `n=400, target=3`).
### Algorithm
1. First, check if the initial number `n` is already beautiful by calculating its digit sum. If `sum(n) <= target`, the minimum addition is `0`.
2. The core idea is to reduce the digit sum by making trailing digits zero. This is done by rounding up to the next multiple of 10, 100, 1000, and so on.
3. Initialize a place value multiplier, `place`, to `10`.
4. Enter a loop that continues until the number becomes beautiful.
5. In each iteration, calculate the number `n` needs to be rounded up to the next multiple of `place`. The value to add, `toAdd`, is `place - (n % place)` (if `n` is not already a multiple of `place`).
6. Add this `toAdd` to `n`. This new `n` is our candidate number.
7. Calculate the digit sum of the new `n`. If it's less than or equal to `target`, we have found our beautiful number. The required `x` is the new `n` minus the original `n`.
8. If the number is still not beautiful, increase the place value by multiplying `place` by 10 and repeat the process.

# Solutions
### Java

```java
class Solution {
public
  long makeIntegerBeautiful(long n, int target) {
    long x = 0;
    while (f(n + x) > target) {
      long y = n + x;
      long p = 10;
      while (y % 10 == 0) {
        y /= 10;
        p *= 10;
      }
      x = (y / 10 + 1) * p - n;
    }
    return x;
  }
private
  int f(long x) {
    int y = 0;
    while (x > 0) {
      y += x % 10;
      x /= 10;
    }
    return y;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long makeIntegerBeautiful(long long n, int target) {
    using ll = long long;
    auto f = [](ll x) {
      int y = 0;
      while (x) {
        y += x % 10;
        x /= 10;
      }
      return y;
    };
    ll x = 0;
    while (f(n + x) > target) {
      ll y = n + x;
      ll p = 10;
      while (y % 10 == 0) {
        y /= 10;
        p *= 10;
      }
      x = (y / 10 + 1) * p - n;
    }
    return x;
  }
};

```

### Python

```python
class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int: def f(x: int) -> int: y = 0 while x: y += x % 10 x //= 10 return y x = 0 while f(n + x) > target: y = n + x p = 10 while y % 10 == 0: y //= 10 p *= 10 x = (y // 10 + 1) * p - n return x

```