Question

2457. 美丽整数的最小增量

English Version

题目描述

给你两个正整数 n 和 target 。

如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个 美丽整数 。

找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

 

示例 1：

输入：n = 16, target = 6
输出：4
解释：最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4 之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。

示例 2：

输入：n = 467, target = 6
输出：33
解释：最初，n 是 467 ，且其每一位数字的和是 4 + 6 + 7 = 17 。在加 33 之后，n 变为 500 且每一位数字的和变成 5 + 0 + 0 = 5 。可以证明无法加上一个小于 33 的非负整数使 n 变成一个美丽整数。

示例 3：

输入：n = 1, target = 1
输出：0
解释：最初，n 是 1 ，且其每一位数字的和是 1 ，已经小于等于 target 。

 

提示：

• 1 <= n <= 1012
• 1 <= target <= 150
• 生成的输入保证总可以使 n 变成一个美丽整数。

解法

方法一：贪心

我们定义函数 $f(x)$ 表示一个整数 $x$ 的每一位数字之和，那么题目求的是 $f(n + x) \leq target$ 的最小非负整数 $x$。

如果 $y = n+x$ 的每一位数字之和大于 $target$，那么我们可以循环通过以下操作，将 $y$ 的每一位数字之和减小到小于等于 $target$：

• 找到 $y$ 的最低位的非零数字，将其减小到 $0$，并将其高一位的数字加 $1$；
• 更新 $x$，继续上述操作，直到 $n+x$ 的每一位数字之和小于等于 $target$。

循环结束，返回 $x$ 即可。

我们可以举个例子，假设 $n=467$, $target=6$，那么 $n$ 的变化过程如下：

$$ \begin{aligned} & 467 \rightarrow 470 \rightarrow 500 \ \end{aligned} $$

时间复杂度 $O(\log^2 n)$，其中 $n$ 给题目给定的整数。空间复杂度 $O(1)$。

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

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;
  }
}

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;
  }
};

func makeIntegerBeautiful(n int64, target int) (x int64) {
  f := func(x int64) (y int) {
    for ; x > 0; x /= 10 {
      y += int(x % 10)
    }
    return
  }
  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
}

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;
}