Problem Description

You are given two positive integers n and target.

An integer is called beautiful if the sum of its digits is less than or equal to target.

Your task is to find the minimum non-negative integer x such that n + x becomes beautiful. In other words, you need to find the smallest value x ≥ 0 where the sum of digits of n + x is at most target.

For example:

• If n = 16 and target = 6, the sum of digits of 16 is 1 + 6 = 7, which is greater than 6. So 16 is not beautiful.
• Adding x = 4 gives us 16 + 4 = 20, with digit sum 2 + 0 = 2 ≤ 6, making 20 beautiful.
• The answer would be 4 since it's the minimum value needed.

The problem guarantees that it's always possible to make n beautiful by adding some non-negative integer to it.

Intuition

The key insight is that to reduce the digit sum of a number, we should increase it to the next "round" number with trailing zeros. Numbers with trailing zeros have smaller digit sums because zeros don't contribute to the sum.

Consider what happens when we want to reduce the digit sum of a number like 467. The digit sum is 4 + 6 + 7 = 17. If we just add small values like 1 or 2, we get 468 or 469, which still have large digit sums. But if we round up to 470, we eliminate the 7 in the ones place, reducing our digit sum to 4 + 7 + 0 = 11.

The strategy is to repeatedly "round up" by eliminating the rightmost non-zero digit. When we change 467 to 470, we're essentially making the last digit 0 and carrying over to the tens place. If the digit sum is still too large, we continue: 470 becomes 500 (eliminating the 7 in the tens place).

Why does this greedy approach work? Because each rounding operation:

1. Reduces the digit sum by eliminating a non-zero digit and replacing it with zero
2. Only increases higher-order digits by at most 1
3. Creates the smallest possible increase that achieves this digit reduction

The algorithm finds the rightmost non-zero digit, rounds up at that position, and repeats until the digit sum meets our target. This ensures we add the minimum value to n because we're making the smallest jumps necessary to reduce the digit sum at each step.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows the greedy strategy of repeatedly rounding up to eliminate non-zero digits from right to left.

First, we define a helper function f(x) that calculates the sum of digits of an integer x:

def f(x: int) -> int:
    y = 0
    while x:
        y += x % 10
        x //= 10
    return y

The main algorithm starts with x = 0 and continues while f(n + x) > target:

1. Calculate current value: Set y = n + x as the current number we're working with.

2. Find the rightmost non-zero digit position:

   • Initialize p = 10 (representing the place value)
   • While y % 10 == 0 (current digit is zero), divide y by 10 and multiply p by 10
   • This loop skips all trailing zeros to find the first non-zero digit from the right

3. Round up to eliminate the non-zero digit:

   • y // 10 + 1 gives us the number after removing the last digit and adding 1
   • Multiply by p to restore the correct place value with trailing zeros
   • Calculate the new x as (y // 10 + 1) * p - n

For example, with n = 467:

• First iteration: y = 467, no trailing zeros, p = 10
  • x = (467 // 10 + 1) * 10 - 467 = 47 * 10 - 467 = 470 - 467 = 3
• Second iteration: y = 470, one trailing zero, p = 100 after the loop
  • x = (47 // 10 + 1) * 100 - 467 = 5 * 100 - 467 = 500 - 467 = 33
• Now f(500) = 5, which is likely ≤ target, so we exit

The algorithm guarantees finding the minimum x because at each step, we make the smallest possible jump that reduces the digit sum by eliminating exactly one non-zero digit.

Example Walkthrough

Let's trace through the algorithm with n = 467 and target = 6.

Initial State:

• n = 467, digit sum = 4 + 6 + 7 = 17 (not beautiful since 17 > 6)
• x = 0

Iteration 1:

• Current value: y = n + x = 467 + 0 = 467
• Digit sum of 467 is 17, which is > 6, so we continue
• Find rightmost non-zero digit:
  • 467 % 10 = 7 (not zero), so p = 10
• Round up: (467 // 10 + 1) * 10 = (46 + 1) * 10 = 470
• Update: x = 470 - 467 = 3

Iteration 2:

• Current value: y = n + x = 467 + 3 = 470
• Digit sum of 470 is 4 + 7 + 0 = 11 (still > 6)
• Find rightmost non-zero digit:
  • 470 % 10 = 0 (is zero), so divide: y = 47, p = 100
  • 47 % 10 = 7 (not zero), stop here with p = 100
• Round up: (47 // 10 + 1) * 100 = (4 + 1) * 100 = 500
• Update: x = 500 - 467 = 33

Iteration 3:

• Current value: y = n + x = 467 + 33 = 500
• Digit sum of 500 is 5 + 0 + 0 = 5 (5 ≤ 6, beautiful!)
• Algorithm terminates

Result: The minimum x = 33 makes 467 + 33 = 500 beautiful.

The algorithm efficiently jumps from 467 → 470 → 500, making the smallest increases needed to reduce the digit sum at each step.

Solution Implementation

Time and Space Complexity

The time complexity is O(log² n), where n is the given integer.

Time Complexity Analysis:

• The outer while loop continues as long as f(n + x) > target. In the worst case, we need to round up n to the next power of 10, which takes at most O(log n) iterations (since we're dealing with digits).
• Inside the outer loop:
  • The function f(x) calculates the sum of digits, which takes O(log(n + x)) time, approximately O(log n) since x is bounded by the next power of 10 relative to n.
  • The inner while loop counts trailing zeros by repeatedly dividing by 10. This loop runs at most O(log n) times (the maximum number of digits).
• Therefore, the total time complexity is O(log n) × O(log n) = O(log² n).

Space Complexity Analysis:

• The algorithm uses only a constant number of variables: x, y, and p.
• The function f(x) also uses only constant extra space for its local variable y.
• No recursive calls or data structures that grow with input size are used.
• Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Large Numbers

Pitfall: When dealing with very large values of n, the intermediate calculations like (current_number // 10 + 1) * multiplier might cause integer overflow in languages with fixed integer sizes. While Python handles arbitrary precision integers automatically, this could be problematic when implementing in languages like Java or C++.

Solution: In languages with fixed integer types, use long/long long data types or implement overflow checking:

# Python handles this automatically, but in other languages:
# Check if multiplication would overflow before performing it
if current_number // 10 + 1 > MAX_VALUE // multiplier:
    # Handle overflow case
    pass

2. Incorrect Handling of Already Beautiful Numbers

Pitfall: The code might perform unnecessary iterations if n is already beautiful. While the while loop condition handles this correctly, developers might accidentally add extra logic that processes already beautiful numbers.

Solution: Always check the condition first:

# Explicitly check if n is already beautiful
if calculate_digit_sum(n) <= target:
    return 0
  
# Then proceed with the main algorithm
addition = 0
while calculate_digit_sum(n + addition) > target:
    # ... rest of the logic

3. Misunderstanding the Rounding Logic

Pitfall: The expression (current_number // 10 + 1) * multiplier might be confusing. Developers might incorrectly think they need to round to the nearest 10, 100, etc., rather than incrementing to the next higher value with trailing zeros.

Example of incorrect approach:

# WRONG: Simply rounding to nearest 10
addition = ((n + 9) // 10) * 10 - n  # This doesn't minimize x

# CORRECT: The algorithm's approach
# Systematically eliminates rightmost non-zero digits

4. Inefficient Digit Sum Calculation

Pitfall: Repeatedly calculating the digit sum from scratch for each iteration can be inefficient, especially for very large numbers with many digits.

Solution: While the current approach is correct, for optimization you could track how the digit sum changes:

def makeIntegerBeautiful(self, n: int, target: int) -> int:
    def calculate_digit_sum(number: int) -> int:
        digit_sum = 0
        while number:
            digit_sum += number % 10
            number //= 10
        return digit_sum
  
    # Cache the initial digit sum
    current_sum = calculate_digit_sum(n)
    if current_sum <= target:
        return 0
      
    addition = 0
    while calculate_digit_sum(n + addition) > target:
        # ... existing logic

5. Edge Case with Small Targets

Pitfall: When target is very small (like 1 or 2), the algorithm might need many iterations to reach a beautiful number, potentially causing performance issues.

Solution: For very small targets, consider jumping directly to powers of 10:

# Special handling for very small targets
if target == 1:
    # Find the next power of 10
    power = 1
    while power <= n:
        power *= 10
    return power - n