MediumNo. 2457
Minimum Addition to Make Integer Beautiful — LeetCode 2457 Python Solution
- Pattern
- Greedy
- Topics
- Greedy, Math
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
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 xComplexity
- Time
- O(log2 n)where n is the integer given in the problem
- Space · auxiliary
- O(1)
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2457. Minimum Addition to Make Integer Beautiful is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0670 | Maximum Swap | Medium |
| 0738 | Monotone Increasing Digits | Medium |
| 0910 | Smallest Range II | Medium |
| 0976 | Largest Perimeter Triangle | Easy |
| 0991 | Broken Calculator | Medium |
| 1217 | Minimum Cost to Move Chips to The Same Position | Easy |
Frequently asked questions
- How hard is LeetCode 2457. Minimum Addition to Make Integer Beautiful?
LeetCode 2457. Minimum Addition to Make Integer Beautiful is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2457. Minimum Addition to Make Integer Beautiful?
The Python solution on this page runs in O(log2 n), where n is the integer given in the problem.
- What is the space complexity of LeetCode 2457. Minimum Addition to Make Integer Beautiful?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2457. Minimum Addition to Make Integer Beautiful cover?
LeetCode 2457. Minimum Addition to Make Integer Beautiful is tagged Greedy and Math on LeetCode.