##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2457.html

# 2457. Minimum Addition to Make Integer Beautiful

• Difficulty: Medium.
• Related Topics: Math, Greedy.
• Similar Questions: Happy Number.

## 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.

## Solution (Java, C++, Python)

• 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 v = 0;
while (x > 0) {
v += x % 10;
x /= 10;
}
return v;
}
}

• using ll = long long;

class Solution {
public:
long long makeIntegerBeautiful(long long n, int target) {
auto f = [](ll x) {
int v = 0;
while (x) {
v += x % 10;
x /= 10;
}
return v;
};
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;
}
};

• class Solution:
def makeIntegerBeautiful(self, n: int, target: int) -> int:
def f(x):
v = 0
while x:
v += x % 10
x //= 10
return v

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


• func makeIntegerBeautiful(n int64, target int) int64 {
f := func(x int64) int {
v := 0
for x > 0 {
v += int(x % 10)
x /= 10
}
return v
}
var x int64
for f(n+x) > target {
y := n + x
var p int64 = 10
for y%10 == 0 {
y /= 10
p *= 10
}
x = (y/10+1)*p - n
}
return x
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).