5 Best Ways to Find the Minimum Positive Integer Divisible by A with Digit Sum B in Python

by

💡 Problem Formulation: We need to find the smallest positive integer that is divisible by a given integer a and has a digit sum equal to another given integer b. For example, if a = 2 and b = 7, the solution would be the integer 14, as it is divisible by 2 and its digits 1 + 4 equals 7.

Method 1: Brute Force Iteration

In the brute force iteration method, we incrementally check each positive integer to see if it meets both conditions: divisibility by a and the sum of digits equal to b. This method continues the search until the integer satisfying both criteria is found, which makes it straightforward but potentially slow for large numbers.

Here’s an example:

def find_min_integer(a, b):
    i = a
    while True:
        if sum(map(int, str(i))) == b and i % a == 0:
            return i
        i += a

# Example usage
a = 2
b = 7
print(find_min_integer(a, b))

Output: 14

This code defines a function find_min_integer() that takes two parameters: a for the divisor and b for the required sum of digits. It starts with the lowest multiple of a and checks each subsequent multiple to see if its digit sum equals b. When both conditions are satisfied, it returns the number.

Method 2: Optimized Brute Force with Sum of Digits Heuristic

Building on the brute force method, we employ a heuristic to skip numbers that cannot have a sum of digits equal to b. For example, we know that any multiple of 10 cannot have a sum of digits more than 9. This optimized approach reduces unnecessary iterations, improving performance.

Here’s an example:

def digit_sum(num):
    return sum(map(int, str(num)))

def find_min_integer_optimized(a, b):
    i = a
    while True:
        if i % 10 == 0 and b > 9:
            i += a * (10 - (i // 10) % 10)
        elif digit_sum(i) == b and i % a == 0:
            return i
        else:
            i += a

# Example usage
a = 2
b = 7
print(find_min_integer_optimized(a, b))

Output: 14

This enhanced function includes a separate helper, digit_sum(), for clarity. The function find_min_integer_optimized() incorporates a check to jump over numbers ending in 0 if b is greater than 9, reducing the number of iterations needed to find the minimal integer.

Method 3: Skip Counting by the Maximum Digit Sum Multiple

This approach starts by finding the smallest multiple of a whose sum of digits could potentially be b. We identify the maximum digit sum multiple of a which is smaller than b and start from there, making the search quicker for certain values of b.

Here’s an example:

def find_min_integer_skip(a, b):
    max_digit_sum = 9 * (len(str(a)) - 1)
    start = (b // max_digit_sum) * a
    for i in range(start, start + a * max_digit_sum, a):
        if digit_sum(i) == b:
            return i
    return None

# Example usage
a = 2
b = 7
print(find_min_integer_skip(a, b))

Output: 14

The function find_min_integer_skip() calculates the maximum possible digit sum for multiples of a and jumps ahead to that number times a. It then checks each subsequent multiple within the range dictated by the digit sum, identifying the minimum positive integer more efficiently.

Method 4: Using Mathematical Insight

When b is less than or equal to 9, the solution is straightforward. For b > 9, we can utilize the fact that we are looking for the smallest number with a digit sum of b. Mathematically, adding a smaller multiple of 9 to the smallest possible number meeting the digit sum b yields potential solutions, which are then validated for divisibility by a.

Here’s an example:

def find_min_integer_math(a, b):
    if b <= 9:
        return b if b % a == 0 else b + a - (b % a)
    base = int('1' + '0' * ((b // 9) - 1))  # smallest number meeting the digit sum
    while True:
        if digit_sum(base) == b and base % a == 0:
            return base
        base += 9 * a  # add a multiple of 9
     
# Example usage
a = 2
b = 7
print(find_min_integer_math(a, b))

Output: 14

The function find_min_integer_math() takes into account the properties of numbers with digit sums and multiples of 9 to find the solution. It checks the smallest number with a digit sum of b and increases it by a multiple of 9 times a until the conditions are met.

Bonus One-Liner Method 5: Lambda with Generator Expression

A compact, one-liner solution using Python’s lambda functions and generator expressions can be used. This is not the most readable or efficient method, but it showcases Python’s ability to create concise expressions for computational problems.

Here’s an example:

find_min_integer_one_liner = lambda a, b: next(i for i in range(a, a * b + 1, a) if sum(map(int, str(i))) == b)

# Example usage
a = 2
b = 7
print(find_min_integer_one_liner(a, b))

Output: 14

This one-liner assigns a lambda function to find_min_integer_one_liner which generates numbers from a to a * b, incrementing by a and checking if the digit sum equals b. The next() function retrieves the first element from the generator that satisfies the condition.

Summary/Discussion

  • Method 1: Brute Force Iteration. Simple and reliable. It can be very slow for large numbers.
  • Method 2: Optimized Brute Force with Heuristic. More efficient than brute force. Still not the best for very large numbers.
  • Method 3: Skip Counting by Maximum Digit Sum Multiple. Faster for large digit sums. Could be less efficient for numbers with smaller digit sums.
  • Method 4: Mathematical Insight. Makes smart use of mathematical properties. Complexity depends on the relationship between a and b.
  • Method 5: One-Liner. A concise solution. It sacrifices readability and is mainly for demonstrating language features.