We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Addition to Make Integer Beautiful

Number: 2544

Difficulty: Medium

Paid? No

Companies: Infosys

Problem Description

Given two positive integers n and target, find the minimum non-negative integer x such that when you add x to n, the resulting number is "beautiful". A number is considered beautiful if the sum of its digits is less than or equal to target.

Key Insights

  • Check if the current number n is already beautiful by summing its digits.
  • If not, try to make n “rounder” by adding just enough to remove the current digit in a particular position (i.e., round up to the nearest multiple of a power of 10).
  • At each digit position, calculate the minimal addition that causes a carry-over, effectively reducing the contribution of lower-order digits.
  • This greedy and iterative rounding approach guarantees that you add the minimum value needed until the digit sum condition is met.

Space and Time Complexity

Time Complexity: O((log n)^2) – In the worst-case scenario, you iterate through each digit position (O(log n)) and compute the digit sum each time (O(log n) digits). Space Complexity: O(1) – Only a few constant-size variables are used.

Solution

The solution works by rounding n up successively by powers of 10. Start by checking n's digit sum; if it meets the condition, return 0. Otherwise, for each position, calculate the remainder with respect to the current power of 10. Use that to determine the increment needed to round n up at that digit position. Add the increment and check again if the updated n is beautiful. Continue until the digit sum is less than or equal to target. Key data structures include integer arithmetic and string conversion (or digit extraction) for the digit sum calculation.

Code Solutions

# Function to calculate the sum of digits of a number
def digit_sum(num):
    return sum(int(digit) for digit in str(num))

def minimum_addition(n, target):
    # If the current number already satisfies the condition, no addition is needed.
    if digit_sum(n) <= target:
        return 0

    add = 0
    power = 1  # Represents the current power of 10 (1, 10, 100, ...)
    while digit_sum(n + add) > target:
        # Calculate how much to add to make current position zero
        remainder = (n + add) % (power * 10)
        increment = (power * 10) - remainder
        add += increment
        power *= 10  # Move to the next digit position
    return add

# Example usage:
print(minimum_addition(16, 6))  # Expected output: 4
← Back to All Questions