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 _minimumnon-negative integer _x such thatn + x is beautiful. The input will be generated such that it is always possible to make n beautiful.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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

Method 1 – Greedy Digit Manipulation

Intuition

To make n beautiful, we want to add the smallest x such that the sum of digits of n + x is ≤ target. The greedy way is to round n up to the next number ending with zeros, check the digit sum, and repeat until the sum is ≤ target.

Approach

  1. If the digit sum of n is already ≤ target, return 0.
  2. Otherwise, for each digit position from least to most significant:
    • Round n up to the next multiple of 10^k.
    • Check if the digit sum is ≤ target.
    • If so, return the difference.
  3. Continue until the condition is met.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    long long makeIntegerBeautiful(long long n, int target) {
        long long ans = 0, base = 1;
        auto digitSum = [](long long x) {
            int s = 0;
            while (x) { s += x % 10; x /= 10; }
            return s;
        };
        while (digitSum(n) > target) {
            long long add = base * (10 - n / base % 10) % (base * 10);
            n += add;
            ans += add;
            base *= 10;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func makeIntegerBeautiful(n int64, target int) int64 {
    ans, base := int64(0), int64(1)
    digitSum := func(x int64) int {
        s := 0
        for x > 0 {
            s += int(x % 10)
            x /= 10
        }
        return s
    }
    for digitSum(n) > target {
        add := base * (10 - (n/base)%10) % (base*10)
        n += add
        ans += add
        base *= 10
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public long makeIntegerBeautiful(long n, int target) {
        long ans = 0, base = 1;
        while (digitSum(n) > target) {
            long add = base * (10 - (n/base)%10) % (base*10);
            n += add;
            ans += add;
            base *= 10;
        }
        return ans;
    }
    private int digitSum(long x) {
        int s = 0;
        while (x > 0) { s += x % 10; x /= 10; }
        return s;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun makeIntegerBeautiful(n: Long, target: Int): Long {
        var ans = 0L
        var base = 1L
        fun digitSum(x: Long): Int {
            var s = 0
            var y = x
            while (y > 0) { s += (y % 10).toInt(); y /= 10 }
            return s
        }
        var num = n
        while (digitSum(num) > target) {
            val add = base * (10 - (num/base)%10) % (base*10)
            num += add
            ans += add
            base *= 10
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def make_integer_beautiful(n: int, target: int) -> int:
    def digit_sum(x: int) -> int:
        s = 0
        while x:
            s += x % 10
            x //= 10
        return s
    ans = 0
    base = 1
    while digit_sum(n) > target:
        add = base * (10 - (n // base) % 10) % (base * 10)
        n += add
        ans += add
        base *= 10
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn make_integer_beautiful(n: i64, target: i32) -> i64 {
        fn digit_sum(mut x: i64) -> i32 {
            let mut s = 0;
            while x > 0 {
                s += (x % 10) as i32;
                x /= 10;
            }
            s
        }
        let mut ans = 0;
        let mut base = 1;
        let mut num = n;
        while digit_sum(num) > target {
            let add = base * (10 - (num/base)%10) % (base*10);
            num += add;
            ans += add;
            base *= 10;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    makeIntegerBeautiful(n: number, target: number): number {
        function digitSum(x: number): number {
            let s = 0;
            while (x > 0) { s += x % 10; x = Math.floor(x / 10); }
            return s;
        }
        let ans = 0, base = 1, num = n;
        while (digitSum(num) > target) {
            const add = base * (10 - Math.floor(num/base)%10) % (base*10);
            num += add;
            ans += add;
            base *= 10;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log n)
    • Each step increases the number of digits.
  • 🧺 Space complexity: O(1)
    • Only a few variables used.