Skip to content

2457. Minimum Addition to Make Integer Beautiful 👍

  • Time: $O(n\log n\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  long long makeIntegerBeautiful(long long n, int target) {
    long ans = 0;
    long power = 1;

    // e.g. n = 123. After tunning off the last bit by adding 7, n = 130.
    // Effectively, we can think n as 13. That's why we do n = (n / 10) + 1.
    while (sum(n) > target) {
      // the cost to turn off the last digit
      ans += power * (10 - n % 10);
      n = n / 10 + 1;
      power *= 10;
    }

    return ans;
  }

 private:
  int sum(long n) {
    int res = 0;
    while (n > 0) {
      res += n % 10;
      n /= 10;
    }
    return res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public long makeIntegerBeautiful(long n, int target) {
    long ans = 0;
    long power = 1;

    // e.g. n = 123. After tunning off the last bit by adding 7, n = 130.
    // Effectively, we can think n as 13. That's why we do n = (n / 10) + 1.
    while (sum(n) > target) {
      // the cost to turn off the last digit
      ans += power * (10 - n % 10);
      n = n / 10 + 1;
      power *= 10;
    }

    return ans;
  }

  private int sum(long n) {
    int res = 0;
    while (n > 0) {
      res += n % 10;
      n /= 10;
    }
    return res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def makeIntegerBeautiful(self, n: int, target: int) -> int:
    ans = 0
    power = 1

    # e.g. n = 123. After tunning off the last bit by adding 7, n = 130.
    # Effectively, we can think n as 13. That's why we do n = (n / 10) + 1.
    while sum(map(int, str(n))) > target:
      # the cost to turn off the last digit
      ans += power * (10 - n % 10)
      n = n // 10 + 1
      power *= 10

    return ans