How do I determine the fewest number of summed integers for a given total in Python?

user_9189577 0
Viewed 63

There is probably an algorithm for this, but I'm not sure what it is.

For an integer X, what are the fewest number of integers whose sum is X, and where the summed integers are less or equal to Y and can be repeated in the sum.

For example:

X=95
Y=1
This is 1 (95 times)

X=39
Y=5
This is 5 (7 times) and 4 (1 time)

X=53
Y=11
This is 11 (4 times), 9 (1 time)

I see that this is kind of recursively dividing the value while reducing the denominator until reaching zero, but there is probably a more elegant method.

UPDATE:

Two things:

  1. I didn't realize that there would not be more than 1 level of division required for this. I assumed that there could be a combination of numerator/denominator where there would be remainders after the 2nd occurrence of the division, but at least in my use case, there isn't.
  2. No, there is nothing Python-specific, it's just what I was using.
math python
3 Answers

You can use divmod() to get the quotient and the remainder:

X = 95
Y = 1

quotient, remainder = divmod(X, Y)
if remainder == 0:
    print(f"This is {Y} ({quotient} times)")
else:
    print(f"This is {Y} ({quotient} times) and {remainder} (1 time)")

This prints:

This is 1 (95 times)
user_177698150 
X=int(input("What is X"))
Y=int(input("What is Y"))

divisor = X // Y # integer divide 
remainder = X % Y

if remainder:
    print(f"This is {Y} ({divisor} times), {remainder}")
else:
    print(f"This is {Y} ({divisor} times)")
user_143313340

What you're asking is to divide one number into another, and provide the remainder.

Using the // operator will divide two numbers, returning a whole number. % operator will provide the remainder when dividing two numbers.

def div(x, y):
    return x//y, x%y


x = 95
y = 15

count, remainder = div(x, y)

text = 'This is {} ({} times)'.format(x, count)

if remainder > 0:
    text += ' and {} ({} times)'.format(remainder, 1)

print(text)
user_159566570
Related