Incrementing while loop isn't working in some test cases

Question

I have to define a function where:

Starting with a positive integer original, keep multiplying original by n and calculate the sum of all multiples generated including original until the sum is no longer smaller than total. Return the minimum number of multiplications needed to reach at value at or above the given total.

So for example:

multiply_until_total_reached (1,5,2)

1*2=2, (1+2)<5, 2*2=4, (1+2+4)>5, 2 multiplications needed
multiply_until_total_reached (1,15,2)

1*2=2, (1+2)<15, 2*2=4, (1+2+4)<15, 4*2=8, (1+2+4+8)=15, 3 multiplications

My current code works but the returned value is off by 1 in some cases. In a 1,1038,2 case, I get 9 multiplication needed instead of 10 but in the 1,15,2 case, I get the correct amount (3) multiplications.

Here's my code:

def multiply_until_total_reached(original, total, n):
    if total < original:
        return 0
    elif total > original:
        sumofdigits = 0 #declares var to keep track of sum of digits to compare to total
        timesofmult = 0 #track how many multiplication operations
        while sumofdigits <= total + 1:
            multnum = original * n
            sumofdigits = multnum + original
            original = multnum
            sumofdigits = sumofdigits + multnum
            timesofmult = timesofmult + 1
        return timesofmult

What's causing it to be off?

You are missing a total == original case. You should probably have if total <= original: return 0. — Bakuriu
– Bakuriu, Commented Mar 6, 2017 at 7:06
I strongly feel there's probably an O(1) or O(logn) solution for this as well if you want it.. — Abhishek J
– Abhishek J, Commented Mar 6, 2017 at 7:14
@AbhishekJebaraj this is the O(log n) solution where n represents the value of total. — EvilTak
– EvilTak, Commented Mar 6, 2017 at 7:21
@EvilTak Ohh.. I meant O(logn n) where n is number of multiplications needed :-P.. It might be overkill in this case though.. Notice how it's corelated with the sum of a GP.. — Abhishek J
– Abhishek J, Commented Mar 6, 2017 at 7:24
@AbhishekJebaraj I know, this can be done in O(1) time using the GP formula and logarithmic inequalities, although that will be slightly more complex if n lies between 0 and 1 and will not work at all if n is negative. This solution is guaranteed to be correct for all n. — EvilTak
– EvilTak, Commented Mar 6, 2017 at 7:30

juanpa.arrivillaga · Accepted Answer · 2017-03-06 07:12:34Z

2

Try this, lot smaller and neater. Explanation is in the comments..

def multiply_until_total_reached(original, total, n):
        sum = original    #Initialize sum to original
        mult_no = 0

        while sum < total:       #Will auto return 0 if original>=total
            sum += original*n    #Add original * n
            original = original*n   #Update the new original
            mult_no += 1    #Increase multiplications by 1

        return mult_no

print multiply_until_total_reached(1,5,2)
print multiply_until_total_reached(1,15,2)
print multiply_until_total_reached(1,1038,2)

#Output
#2
#3
#10

edited Mar 6, 2017 at 7:12

juanpa.arrivillaga

97.6k14 gold badges141 silver badges190 bronze badges

answered Mar 6, 2017 at 7:06

Abhishek J

2,6143 gold badges24 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Jan Christoph Terasa Over a year ago

While this solves the problem in a more concise way, it does not really answer the question, and does not help the OP to understand.

Abhishek J Over a year ago

Yeah, If he was a student and wanted to learn and find out his mistakes this wouldn't be of much help.. but if he was working and wanted some neater code and a quick answer this would help him a lot imo..

Prithvi Boinpally Over a year ago

Honestly, I was reading this code and it makes perfect sense to me. It's just a different (and faster/cleaner) approach to the problem. I understood my error as Evil Tak explained it below.

EvilTak · Accepted Answer · 2017-03-06 07:09:05Z

2

Your problem is that you are reassigning sumofdigits in every loop iteration. You just have to add multnum to sumofdigits in every iteration (sumofdigits += multnum). Also, your loop condition needs to be fixed to sumofdigits < total since you have to "Return the minimum number of multiplications needed to reach at value or above the given total."

answered Mar 6, 2017 at 7:09

EvilTak

7,88232 silver badges38 bronze badges

2 Comments

Prithvi Boinpally Over a year ago

Oh ok that makes sense. So I must delete the first sumofdigits = multnum + original and just use the sumofdigits += multnum? TIA

EvilTak Over a year ago

@Pritster5 yes.

Guillaume · Accepted Answer · 2017-03-06 09:31:01Z

1

Since solution for your code has already been posted, and you accept alternative solutions, allow me to suggest the following, which makes good use of Python's > 3.2 accumulate() function:

from itertools import accumulate, count

def multiply_until_total_reached(original, total, n):
    for i, result in enumerate(accumulate(original*n**c for c in count())):
        if result >= total: return i

assert multiply_until_total_reached(1,5,2) == 2
assert multiply_until_total_reached(1,15,2) == 3
assert multiply_until_total_reached(1,1038,2) == 10

answered Mar 6, 2017 at 9:31

Guillaume

6,1293 gold badges28 silver badges48 bronze badges

1 Comment

Prithvi Boinpally Over a year ago

I appreciate the solution but unfortunately I was not allowed to use such functions in the code.

Collectives™ on Stack Overflow

Incrementing while loop isn't working in some test cases

3 Answers 3

3 Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related