CODEWITHSUNDEEP
pythonpython-3.xalgorithm
Mahir Islam
Mahir Islam

Reputation: 1972

Is there a more effective implementation?

Problem statement:

You are given two positive integers d and s . Find minimal positive integer n which is divisible by d and has sum of digits equal to s .

Input:

The first line contains two positive integers d and s ( 1 ≤ d ≤ 500 , 1 ≤ s ≤ 5000 ) separated by space.

Output:

Print the required number or -1 if it doesn't exist.

This my code:

d_and_s = [int(x) for x in input().split()]
counter_dracula = 0
while True:
    if counter_dracula%d_and_s[0] == 0 and sum(map(int, str(counter_dracula))) == d_and_s[1]:
        break
     counter_dracula += 1
     print(counter_dracula)

That's my implementation but clearly there must be a faster way. For example if the Input is 13 and 50 the output is 699998. My code gives me the correct answer but takes a long time but even ultra longer in this sample testcase: Input is 61 and 2 and the output is 1000000000000000000000000000001.

How can I implement them correctly using Python 3?

Upvotes: 0

Views: 82

Answers (1)

Christian Sloper
Christian Sloper

Reputation: 7510

(yey, the question opened again :-) )

For one quite improvement, realize that the numbers divisible by d is d, 2*d, 3*d, 4*d , ...

So instead of incrementing the loop by 1 every time, you can increment with d

def sum_digits(n):
   r = 0
   while n:
       r, n = r + n % 10, n // 10
   return r

d, s = [int(x) for x in input().split()]

counter = 0

while True:
    counter += d
    if sum_digits(counter) == s:
        break
print(counter)

Upvotes: 2

Related Questions