Minimum Addition to Make Integer Beautiful

Minimum Addition to Make Integer Beautiful - Problem

Math Greedy Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 16, target = 6

› Output: 4

💡 Note: n=16 has digit sum 1+6=7 > 6. Adding 4 gives us 20 with digit sum 2+0=2 ≤ 6.

Example 2 — Already Beautiful

$ Input: n = 467, target = 20

› Output: 0

💡 Note: n=467 has digit sum 4+6+7=17 ≤ 20, so it's already beautiful.

Example 3 — Large Rounding

$ Input: n = 1, target = 1

› Output: 0

💡 Note: n=1 has digit sum 1 ≤ 1, so it's already beautiful.

Constraints

1 ≤ n ≤ 10¹²
1 ≤ target ≤ 150

Visualization

Tap to expand

Understanding the Visualization

Input

Number n=16, target=6

Process

Current sum=7>6, need to reduce

Output

Add 4 to get 20 with sum=2≤6

Key Takeaway

🎯 Key Insight: Rounding up digits to powers of 10 can drastically reduce digit sum with minimal addition

Asked in

G Google 12 M Microsoft 8 a Amazon 5

The key insight is that rounding up digits to the next power of 10 can dramatically reduce digit sum. The greedy approach finds the optimal position to round up. Time: O(log n), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(x × log(n+x))	O(1)	Try adding 0, 1, 2, 3... until digit sum ≤ target
Greedy Digit Rounding	O(log n)	O(log n)	Round up digits from right to left to minimize total addition

Brute Force — Algorithm Steps

Start with x = 0
Calculate digit sum of n + x
If digit sum ≤ target, return x
Otherwise increment x and repeat

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with x=0, check if n+0 is beautiful

Increment

If not beautiful, try x=1, x=2, x=3...

Found

Return first x where digit sum ≤ target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int digitSum(long long num) {
    int total = 0;
    while (num > 0) {
        total += num % 10;
        num /= 10;
    }
    return total;
}

long long solution(long long n, int target) {
    long long x = 0;
    while (digitSum(n + x) > target) {
        x++;
    }
    return x;
}

int main() {
    long long n;
    int target;
    scanf("%lld", &n);
    scanf("%d", &target);
    printf("%lld\n", solution(n, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(x × log(n+x))

We may need to try up to x values, and calculating digit sum takes O(log(number)) time

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables for counting

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler