A man smokes cigarettes. He smokes 3/4 of each cigarette and dumps the remaining 1/4.

You are given the number of cigarettes he starts with. You need to write a program to find the total number of cigarettes he can smoke. Smoking 3/4 of a cigarette counts and 1, and if he has access to a whole cigarette worth of dumped quarters, he will smoke 3/4 of that, leaving an additional quarter.

For example, if the starting count S is 4, he smokes all four, and dumps 4*1/4=1 cigarette, which he then smokes. So the total number of cigarettes smoked is 5.

For S=16, he smokes 16, leaving 4 whole cigarettes, which he smokes, leaving an addition 1, which he smokes, for a total of 21.

CodePudding user response：

def count_cigs(n): 
    res = 0 
    rem = 0 
    while n: 
        rem  = n%4  
        res  = n 
        n //= 4 
        n  = rem//4  
        rem %= 4 
    res  = rem//4  
    return res

2 tests:

In [5]: count_cigs(4)                                                                                                  
Out[5]: 5

In [6]: count_cigs(16)                                                                                                 
Out[6]: 21

The idea is this:

1. At each step, you add the number of n, which are whole cigarettes, to the result.
2. You keep track of the remainder of the number of cigarettes divided by 4 and add that to the remainder of the previous iteration. This is necessary because over time remainders can accumulate to whole cigarettes (when they are integer divisible by 4).
3. You set n to the result of it integer divided by 4. That's the number of whole remaining cigarettes.
4. Now you integer divide the remainder by 4, for the case that it has accumulated to whole cigarettes, and add it to the number of cigarettes.
5. You set the remainder of cigarettes to the remainder of it divided by 4.
6. At last, when whole cigarettes are equal to zero and we are out of the loop, you add any whole cigarettes remaining in the remainder to the result.

The algorithm runs in O(log n), since at each step we divide n by 4.