Question

2457. Minimum Addition to Make Integer Beautiful

中文文档

Description

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.

Solutions

Solution 1: Greedy Algorithm

We define a function $f(x)$ to represent the sum of the digits of an integer $x$. The problem is to find the minimum non-negative integer $x$ such that $f(n + x) \leq target$.

If the sum of the digits of $y = n+x$ is greater than $target$, we can loop through the following operations to reduce the sum of the digits of $y$ to less than or equal to $target$:

• Find the lowest non-zero digit of $y$, reduce it to $0$, and add $1$ to the digit one place higher;
• Update $x$ and continue the above operation until the sum of the digits of $n+x$ is less than or equal to $target$.

After the loop ends, return $x$.

For example, if $n=467$ and $target=6$, the change process of $n$ is as follows:

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

The time complexity is $O(\log^2 n)$, where $n$ is the integer given in the problem. The space complexity is $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;
}