LeetCode 2457 - Minimum Addition to Make Integer Beautiful

The problem asks us to transform a given integer n into a beautiful integer by adding the smallest non-negative integer x. An integer is defined as beautiful if the sum of its digits is less than or equal to a given target.

leetcodemediummathgreedy

LeetCode Problem 2457

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to transform a given integer n into a beautiful integer by adding the smallest non-negative integer x. An integer is defined as beautiful if the sum of its digits is less than or equal to a given target. The input consists of two numbers: n (the original number) and target (the maximum allowed digit sum). The output is the minimum x such that n + x becomes beautiful.

The constraints indicate that n can be as large as 10^12 and target up to 150. This means any naive approach that iterates one by one from n upwards is impractical due to potential large input sizes. Important edge cases include scenarios where n is already beautiful (so x should be 0), n has many digits, or the sum of digits is just slightly above target. The problem guarantees a solution exists, so we do not need to handle impossible cases.

Approaches

A brute-force approach would be to check each successive integer starting from n and calculate its digit sum until it becomes beautiful. This approach is correct but extremely slow for large values of n, as computing each digit sum and iterating could take up to 10^12 iterations.

The key insight for an optimal solution comes from observing how digit sums change when we "round up" the number to the next multiple of a power of ten. By progressively zeroing out digits from the least significant side and incrementing higher-order digits, we can minimize the added number while ensuring the resulting integer's digit sum does not exceed target. Essentially, we are simulating a carry operation to create the smallest beautiful number.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * log n) O(1) Increment n until sum of digits <= target. Too slow for large n.
Optimal O(log n) O(1) Round up n digit by digit to the next multiple of 10^k until digit sum <= target.

Algorithm Walkthrough

  1. Compute the sum of digits of n. If it is already <= target, return 0 because n is already beautiful.

  2. Initialize factor to 1. This represents the current power of ten we are rounding up to.

  3. Loop while the sum of digits of the working number is greater than target:

  4. Compute increment = factor - (n % factor). This is the smallest number needed to round up the least significant digits to zero.

  5. Add increment to n.

  6. Multiply factor by 10 to move to the next higher digit.

  7. Once the sum of digits of n is <= target, return the accumulated sum of increments as the minimum x.

Why it works: By incrementally rounding up the number, we ensure that we remove low-order digits that contribute excessively to the sum while increasing higher digits minimally. This guarantees that the resulting number is the smallest possible beautiful number, and the sum of increments gives the minimum x.

Python Solution

class Solution:
    def makeIntegerBeautiful(self, n: int, target: int) -> int:
        def digit_sum(num: int) -> int:
            total = 0
            while num > 0:
                total += num % 10
                num //= 10
            return total
        
        if digit_sum(n) <= target:
            return 0
        
        result = 0
        factor = 1
        
        while digit_sum(n) > target:
            increment = factor - (n % factor)
            n += increment
            result += increment
            factor *= 10
        
        return result

The code first defines a helper function to compute the sum of digits. If n is already beautiful, it returns 0. Otherwise, it iteratively rounds up n to the next multiple of increasing powers of ten, accumulating the total increment, until the digit sum condition is satisfied.

Go Solution

func makeIntegerBeautiful(n int64, target int) int64 {
    digitSum := func(num int64) int {
        sum := 0
        for num > 0 {
            sum += int(num % 10)
            num /= 10
        }
        return sum
    }
    
    if digitSum(n) <= target {
        return 0
    }
    
    var result int64 = 0
    factor := int64(1)
    
    for digitSum(n) > target {
        increment := factor - (n % factor)
        n += increment
        result += increment
        factor *= 10
    }
    
    return result
}

The Go implementation mirrors Python's logic. It defines a closure digitSum for computing digit sums, handles large integers with int64, and uses the same rounding strategy with cumulative increment.

Worked Examples

Example 1: n = 16, target = 6

Step n factor increment sum_digits(n)
Init 16 1 - 7
1 20 10 4 2

Result: 4

Example 2: n = 467, target = 6

Step n factor increment sum_digits(n)
Init 467 1 - 17
1 470 10 3 11
2 500 100 30 5

Result: 33

Example 3: n = 1, target = 1

Step n factor increment sum_digits(n)
Init 1 1 - 1

Result: 0

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Each iteration increases the factor by 10, so the loop runs at most log10(n) times. Each digit sum computation is O(log n).
Space O(1) Only a few integer variables are used.

The solution is efficient even for n up to 10^12 because the number of digits is small, and the iterative rounding approach reduces the number of necessary checks dramatically.

Test Cases

# Provided examples
assert Solution().makeIntegerBeautiful(16, 6) == 4  # example 1
assert Solution().makeIntegerBeautiful(467, 6) == 33  # example 2
assert Solution().makeIntegerBeautiful(1, 1) == 0  # example 3

# Edge cases
assert Solution().makeIntegerBeautiful(999, 1) == 1  # rounds to 1000
assert Solution().makeIntegerBeautiful(10**12, 1) == 10**12  # max n
assert Solution().makeIntegerBeautiful(19, 10) == 1  # sum goes from 10 to 20, rounds to 20
assert Solution().makeIntegerBeautiful(123456789, 45) == 0  # already beautiful, sum = 45
Test Why
n = 16, target = 6 Basic rounding example
n = 467, target = 6 Multiple rounding steps
n = 1, target = 1 Already beautiful
n = 999, target = 1 Rounding causes digit expansion
n = 10^12, target = 1 Maximum n stress test
n = 19, target = 10 Minimal increment needed
n = 123456789, target = 45 Already beautiful

Edge Cases

One edge case occurs when n is already beautiful. A naive algorithm might still attempt increments, but our solution checks the digit sum first and immediately returns 0. Another case is when the increment causes a carry that increases the number of digits, such as 999 → 1000. The factor-based rounding handles this correctly by computing the proper increment at each digit level. Finally, very large numbers near 10^12 could cause performance issues with brute-force methods, but the logarithmic iteration ensures efficiency.