Minimum addition to make integer beautiful

Math Greedy

38.6% acceptance

Feb 25, 2026

549

You are given two positive integers n and target. An integer is considered beautiful if the sum of its digits is less than or e qual to target. * Return the minimum non-negative integer x such that n + x is beautiful. The i nput will be generated such that it is always possible to make n beautiful. *

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

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
    }
    if digit_sum(n) <= target { return 0; }
    // Round up: for offset=10,100,1000,..., round n up to next multiple of offset
    let mut offset = 10i64;
    loop {
      let rounded = (n / offset + 1) * offset;
      if digit_sum(rounded) <= target {
        return rounded - n;
      }
      offset *= 10;
    }
  }
}