Minimum Addition to Make Integer Beautiful - Solution & Explanation
Problem Statement
You are given two positive integers n and target.
An integer is considered beautiful if the sum of its digits is less than or equal to target.
Return the minimum non-negative integer x such that n + x is beautiful. The input will be generated such that it is always possible to make n beautiful.
Example 1:
Input: n = 16, target = 6 Output: 4 Explanation: 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 Explanation: 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 Explanation: Initially n is 1 and its digit sum is 1, which is already smaller than or equal to target.
Constraints:
1 <= n <= 10121 <= target <= 150- The input will be generated such that it is always possible to make
nbeautiful.
Approach Overview
Problem Overview: You are given an integer n and a target digit sum target. The task is to add the smallest possible non‑negative integer x so that the digit sum of n + x becomes less than or equal to target. The result must be the minimum addition that satisfies the constraint.
Approach 1: Incremental Addition and Digit Sum Check (Time: O(k * d), Space: O(1))
The straightforward strategy repeatedly increases the number until its digit sum becomes valid. Start with x = 0, compute the digit sum of n + x, and keep incrementing until the sum is ≤ target. Each iteration recalculates the digit sum by extracting digits using modulo and division. This approach directly simulates the requirement and is easy to implement, but it may require many increments when the next valid number is far away. Time complexity depends on the number of increments k and the digit count d, while space remains constant.
Approach 2: Jump to Nearest Power of Ten (Greedy) (Time: O(d), Space: O(1))
The optimal solution uses a greedy observation about decimal numbers. Instead of incrementing one by one, push the number to the next "clean" boundary where a digit becomes zero after carry propagation. Traverse digits from right to left. Whenever the current digit causes the total digit sum to exceed target, round the number up to the next multiple of 10^k. This effectively sets trailing digits to zero and adds the required carry to the higher position. Continue this process until the digit sum becomes ≤ target. Each step reduces the digit sum significantly, which guarantees only a few iterations proportional to the number of digits.
This greedy rounding works because any minimal addition must eventually eliminate problematic digits from the least significant side. By jumping directly to the next power-of-ten boundary, you skip unnecessary intermediate numbers while preserving the smallest possible increase.
The algorithm uses simple arithmetic operations from math: compute digit sums, track powers of ten, and apply modulo to isolate trailing digits. Because you only scan through the digits of n and occasionally propagate carries, the runtime stays linear in the number of digits.
Recommended for interviews: Interviewers expect the greedy rounding solution. The incremental simulation shows you understand the requirement, but the power-of-ten jump demonstrates number manipulation skills and greedy reasoning. It also achieves optimal O(d) time with O(1) extra space, which is the standard editorial solution.
Approach 1: Approach 1: Incremental Addition and Digit Sum Check
The core idea is to incrementally add numbers starting from 0 until the sum of the digits of the new number is less than or equal to the target. This method continuously checks if the current number plus increment makes it beautiful.
This is a straightforward implementation but can be inefficient for large n, especially if n itself has a large digit sum initially that needs significant addition to become beautiful.
We define a helper function digit_sum to calculate the sum of digits of a number. Then, starting from x = 0, the function increments x until the sum of the digits of n + x becomes less than or equal to target.
Complexity
Time Complexity: O(d * k), where d is the number of digits in number and k is the number of increments needed.
Space Complexity: O(1), since we are using a constant amount of extra space.
Approach 2: Approach 2: Jump to Nearest Power of Ten
This method makes use of the observation that adding up to the next multiple of 10, 100, etc., could quickly reduce the digit sum due to the carry-over effect smoothing out non-zero digits. We compute the additional amount required to reach the next power of 10, evaluate if this results in a beautiful number, and use this tactic iteratively.
Rather than increment by 1, this solution calculates the difference needed to reach the next power of 10 from the current value, adds it to both x and n, and checks if the new number is beautiful. It repeats until the condition is satisfied.
Complexity
Time Complexity: O(d), where d is the number of digits since each jump reduces digits considerably.
Space Complexity: O(1).
Approach 3: 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.
If the sum of the digits of y = n+x is greater than target, we can loop through the following operations to reduce the sum of the digits of y to less than or equal to target:
- Find the lowest non-zero digit of
y, reduce it to0, and add1to the digit one place higher; - Update
xand continue the above operation until the sum of the digits ofn+xis less than or equal totarget.
After the loop ends, return x.
For example, if n=467 and target=6, the change process of n is as follows:
$
\begin{aligned}
& 467 \rightarrow 470 \rightarrow 500 \
\end{aligned}
The time complexity is O(log^2 n), where n is the integer given in the problem. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Incremental Addition and Digit Sum Check | Time Complexity: Space Complexity: |
| Approach 2: Jump to Nearest Power of Ten | Time Complexity: Space Complexity: |
| Greedy Algorithm | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Incremental Addition and Digit Sum Check | O(k * d) | O(1) | Conceptual brute-force approach or when demonstrating the basic idea before optimization |
| Jump to Nearest Power of Ten (Greedy) | O(d) | O(1) | Best general solution; minimizes additions by rounding digits and propagating carries |
Video Solution
2457. Minimum Addition to Make Integer Beautiful | Weekly Contest 317 | LeetCode 2457 • Bro Coders • 1,529 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Addition to Make Integer Beautiful easy or hard?
Minimum Addition to Make Integer Beautiful Python/Java solution
How to solve Minimum Addition to Make Integer Beautiful in O(n)?
What is the best approach for Minimum Addition to Make Integer Beautiful?
Is Minimum Addition to Make Integer Beautiful asked at Google/Amazon/Meta?
What data structure is used in Minimum Addition to Make Integer Beautiful?
What is the time complexity of Minimum Addition to Make Integer Beautiful?
Ready to solve this problem?
Practice Minimum Addition to Make Integer Beautiful with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor