#2457

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Addition to Make Integer Beautiful

Find the minimum addition to a number such that its digits sum to a value less than or equal to a given target.

Problem Statement

You are given two positive integers, n and target. Your task is to return the smallest non-negative integer x such that when added to n, the resulting number's digit sum is less than or equal to target.

An integer is considered beautiful if the sum of its digits is less than or equal to the target. You need to ensure that no unnecessary addition occurs, and the result should be the minimal x for the solution.

Examples

Example 1

Input: n = 16, target = 6

Output: 4

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

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

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.

Solution Approach

Greedy Choice and Validation

This problem can be solved using a greedy approach by checking each digit of n. If the sum of the digits is greater than the target, adjust the least significant digits by adding a value that reduces the sum. The solution increments the digits step-by-step to find the minimal x.

Breaking Down Digits Independently

Each digit of n can be considered independently, which means each individual digit's contribution to the total sum must be reduced to meet the target. By examining each place value, you can add the necessary value to minimize the addition needed.

Efficient Calculation of x

A direct approach to calculate x can be implemented by examining the sum of digits and calculating the required addition for each place value of n. This ensures minimal computation by focusing only on the necessary changes to the number.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the number of digits in n, which is proportional to the logarithm of n. Specifically, the time complexity is O(d), where d is the number of digits in n, and the space complexity is O(1) since we only require a fixed amount of extra space for calculations.

What Interviewers Usually Probe

Interviewee demonstrates understanding of digit-based greedy strategies.
Candidate identifies the importance of considering each digit independently.
Solver maintains efficiency with a logarithmic approach to the number of digits.

Common Pitfalls or Variants

Common pitfalls

Forgetting to consider the sum of digits at each place value independently.
Not minimizing the addition when examining possible values for x.
Misunderstanding the problem constraints and incorrectly assuming the addition could be larger.

Follow-up variants

What if the target were negative or zero?
What if n is very large, approaching the upper limits of the constraint?
What if the target was set to be much larger than the sum of digits of n?

FAQ

What is the approach for solving the Minimum Addition to Make Integer Beautiful problem?

The approach involves examining each digit independently and using a greedy method to find the minimum x that makes the digit sum less than or equal to the target.

Why is the greedy method used in this problem?

The greedy approach works because it allows us to incrementally adjust each digit, ensuring the smallest necessary change to make the sum of digits meet the target.

What are the main pitfalls when solving this problem?

Common pitfalls include not accounting for each digit separately or not minimizing the addition required to make the sum of digits meet the target.

How does GhostInterview assist in solving this problem?

GhostInterview provides structured guidance on breaking down the problem, helping you understand the greedy approach and avoid common mistakes.

What is the time complexity of solving this problem?

The time complexity is O(d), where d is the number of digits in n. This is efficient due to the logarithmic nature of digit analysis.

terminal

Solution

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#2541 minimum operations to make array equal ii #2366 minimum replacements to sort the array #2358 maximum number of groups entering a competition