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
}

  • function makeIntegerBeautiful(n: number, target: number): number {
    const f = (x: number): number => {
        let y = 0;
        for (; x > 0; x = Math.floor(x / 10)) {
            y += x % 10;
        }
        return y;
    };

    let x = 0;
    while (f(n + x) > target) {
        let y = n + x;
        let p = 10;
        while (y % 10 === 0) {
            y = Math.floor(y / 10);
            p *= 10;
        }
        x = (Math.floor(y / 10) + 1) * p - n;
    }
    return x;
}

Explain:

nope.

Complexity:

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

All Problems

All Solutions