2457. Minimum Addition to Make Integer Beautiful LeetCode Solution
In this guide, you will get 2457. Minimum Addition to Make Integer Beautiful LeetCode Solution with the best time and space complexity. The solution to Minimum Addition to Make Integer Beautiful problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Addition to Make Integer Beautiful
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.
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 <= 1012
1 <= target <= 150
The input will be generated such that it is always possible to make n beautiful.
Complexity Analysis
Time Complexity: O(n\log n\log n)
Space Complexity: O(1)
2457. Minimum Addition to Make Integer Beautiful LeetCode Solution in C++
class Solution {
public:
long long makeIntegerBeautiful(long long n, int target) {
long ans = 0;
long power = 1;
// e.g. n = 123. After tunning off the last bit by adding 7, n = 130.
// Effectively, we can think n as 13. That's why we do n = (n / 10) + 1.
while (sum(n) > target) {
// the cost to turn off the last digit
ans += power * (10 - n % 10);
n = n / 10 + 1;
power *= 10;
}
return ans;
}
private:
int sum(long n) {
int res = 0;
while (n > 0) {
res += n % 10;
n /= 10;
}
return res;
}
}; /* code provided by PROGIEZ */
2457. Minimum Addition to Make Integer Beautiful LeetCode Solution in Java
class Solution {
public long makeIntegerBeautiful(long n, int target) {
long ans = 0;
long power = 1;
// e.g. n = 123. After tunning off the last bit by adding 7, n = 130.
// Effectively, we can think n as 13. That's why we do n = (n / 10) + 1.
while (sum(n) > target) {
// the cost to turn off the last digit
ans += power * (10 - n % 10);
n = n / 10 + 1;
power *= 10;
}
return ans;
}
private int sum(long n) {
int res = 0;
while (n > 0) {
res += n % 10;
n /= 10;
}
return res;
}
} // code provided by PROGIEZ
2457. Minimum Addition to Make Integer Beautiful LeetCode Solution in Python
class Solution:
def makeIntegerBeautiful(self, n: int, target: int) -> int:
ans = 0
power = 1
# e.g. n = 123. After tunning off the last bit by adding 7, n = 130.
# Effectively, we can think n as 13. That's why we do n = (n / 10) + 1.
while sum(map(int, str(n))) > target:
# the cost to turn off the last digit
ans += power * (10 - n % 10)
n = n // 10 + 1
power *= 10
return ans # code by PROGIEZ
