# Lovely Lucky LAMBs

I am trying to solve this question from google's foobar. However, my code exceeds the time limit, even though when I tested it I got correct answers. How can I make my code more efficient?

# Lovely Lucky LAMBs

Being a henchman isn't all drudgery. Occasionally, when Commander Lambda is feeling generous, she'll hand out Lucky LAMBs (Lambda's All-purpose Money Bucks). Henchmen can use Lucky LAMBs to buy things like a second pair of socks, a pillow for their bunks, or even a third daily meal!

However, actually passing out LAMBs isn't easy. Each henchman squad has a strict seniority ranking which must be respected - or else the henchmen will revolt and you'll all get demoted back to minions again!

There are 4 key rules which you must follow in order to avoid a revolt: 1. The most junior henchman (with the least seniority) gets exactly 1 LAMB. (There will always be at least 1 henchman on a team.) 2. A henchman will revolt if the person who ranks immediately above them gets more than double the number of LAMBs they do. 3. A henchman will revolt if the amount of LAMBs given to their next two subordinates combined is more than the number of LAMBs they get. (Note that the two most junior henchmen won't have two subordinates, so this rule doesn't apply to them. The 2nd most junior henchman would require at least as many LAMBs as the most junior henchman.) 4. You can always find more henchmen to pay - the Commander has plenty of employees. If there are enough LAMBs left over such that another henchman could be added as the most senior while obeying the other rules, you must always add and pay that henchman.

Note that you may not be able to hand out all the LAMBs. A single LAMB cannot be subdivided. That is, all henchmen must get a positive integer number of LAMBs.

Write a function called answer(total_lambs), where total_lambs is the integer number of LAMBs in the handout you are trying to divide. It should return an integer which represents the difference between the minimum and maximum number of henchmen who can share the LAMBs (that is, being as generous as possible to those you pay and as stingy as possible, respectively) while still obeying all of the above rules to avoid a revolt. For instance, if you had 10 LAMBs and were as generous as possible, you could only pay 3 henchmen (1, 2, and 4 LAMBs, in order of ascending seniority), whereas if you were as stingy as possible, you could pay 4 henchmen (1, 1, 2, and 3 LAMBs). Therefore, answer(10) should return 4-3 = 1.

To keep things interesting, Commander Lambda varies the sizes of the Lucky LAMB payouts: you can expect total_lambs to always be between 10 and 1 billion (10 ^ 9).

# Languages

To provide a Python solution, edit solution.py To provide a Java solution, edit solution.java

# Test cases

Inputs: (int) total_lambs = 10 Output: (int) 1

Inputs: (int) total_lambs = 143 Output: (int) 3

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

def answer(lambs):
totals = [generous(lambs), stingy(lambs)]
difference = max(totals) - min(totals)
return difference

def generous(lambs):
num = 1
while True:
total = 2**(num) - 1
if total <= lambs:
num += 1
else:
num -= 1
break
return num

def stingy(lambs):
num = 1
while True:
total = (fibonacci(num + 2) - 1)
if total <= lambs:
num += 1
else:
num -= 1
break
return num

def fibonacci(num):
if num > -1 and num < 3:
return 1
else:
num = fibonacci(num - 1) + fibonacci(num - 2)
return num

• Welcome to codereview. What python version are you using? Commented Sep 2, 2017 at 8:28

Slightly longer answer: don't use recursion if you have more than a single recursive call of your function in the non-trivial paths without memoization.

Your fibonacci calls itself twice, except when num is in range(0,3). Those two calls will call fibonacci again twice (unless one of them is already in your base case), so we now end up with four calls. Let's have a look at fibonacci(5) for example:

fibonacci(5) = fibonacci(5 - 1) + fibonacci(5 - 2)
=   (fibonacci((5 - 1) - 1) + fibonacci((5 - 1) - 2))
+ (fibonacci((5 - 2) - 1) + fibonacci((5 - 2) - 2))
=   (fibonacci(((5 - 1) - 1) - 1) + fibonacci(((5 - 1) - 1) - 2)
+ fibonacci((5 - 1) - 2))
)
+ (fibonacci((5 - 2) - 1) + fibonacci((5 - 2) - 2))
=   fibonacci(2) + fibonacci(1) + fibonacci(2)
+ fibonacci(2) + fibonacci(1)


We end up with five calls of the base case, which is what you would expect. But if we count the in-between calls, we get 9 calls for num = 5, 15 calls for num = 6, 25 calls for num = 7. The number of calls increases by a factor of $1.618$.

This is called an exponential time algorithm, because its runtime has the asymptotic behaviour of $\mathcal O (1.618^{n})$. The recursive variant looks great on paper, and it's how Fibonacci numbers are defined after all, but the run-time is ungodly.

One can speed the recursive variant up if we would remember the values; if we calculate fib(5), we can remember the result of fib(3) that we need in fib(4) = fib(3) + fib(2) for our later use in fib(5) = fib(4) + fib(3). That process is called memoization, but it's an overkill and not easy to implement.

Instead, write fibonacci in an iterative fashion:

def fibonacci(num):
""""Returns the num-th fibonacci number, 1-indexed.

The Fibonacci sequence follows the following rules:

1) The first number is 1
2) The second number is 1
3) Every other number is the sum of its two predecessors

This yields the sequence

1,1,2,3,5,8,13,21,34,...
"""
a,b = 1,1

for _ in range(0,num):
a, b = b, a + b

return a


Other than that, your code seems fine. You could use better names and documentation, but given that you write code for a code challenge, it's not that necessary. You might want to use a binary search for your limits, though, if you need more speed.

In generous, you can speed things up if you use bitshifts instead of 2**num.

You can speed up stingy if you calculate the Fibonacci numbers there. That prevents you from calculating the same sequence over and over again. Hint: you can implement fibonacci as a generator, which makes this a lot easier.

• BTW to make it faster I used memorization so it stores results that are already calculated to a list.
– ngmh
Commented Sep 9, 2017 at 12:23
• @ngmh I know I'm 2 years late, but if you use the closed form formula for F_n, you can make it (essentially) O(1) instead of O(n). F(n)=round((phi^n)/sqrt(5)) where phi=(sqrt(5)+1)/2. Commented Apr 12, 2020 at 4:06
• @vikarjramun Unfortunately, the closed formula will differ from the correct answer, as the irrational number $\sqrt{5}$ cannot get represented with only finite bits (e.g. a IEEE 754 double, which is what python uses). Your $F(N)$ will differ around $N\approx 72$, because that's when the IEE 754's precisions will be exhausted. It's fine for this challenge, since the result will never exceed $10^9$ (and $\log_2(10^9) < 30$), but one must keep that in mind if they need correct results.
– Zeta
Commented Apr 12, 2020 at 7:55
• @Zeta Ah, that makes sense. Actually, I'm coincidentally struggling on this exact challenge (which is how I found this question). I thought I had a clever O(1) solution (with its constraints), but it is failing. I used an inverse fibbonacci function I(n) = floor(log(n*sqrt(5)+0.5)/log(phi)) (which I think is accurate), but I'm getting a wrong answer verdict on only 2 out of 10 of the test cases. Do you think I'm hitting the IEEE floating point precision limit here? Or is my formula just inaccurate for large values of n? Commented Apr 13, 2020 at 1:36

Building upon @Zeta excellent answer, if you turn fibonacci into a generator, you only need to sum each term in stingy and stop when the sum is higher than the amount of lambs. The number of sums being the number of henchmen you can hire. To do so efficiently, you can use itertools.accumulate.

You are also reinventing the wheel in generous as what you are computing is a base 2 logarithm.

Lastly, it's pretty clear in the question that the stingy strategy will always give you more henchmen than the generous one. So there is no need for min and max here. But even if you want to be sure, you'd rather use abs instead.

Proposed improvements:

from math import log2
from itertools import accumulate

return stingy(lambs) - generous(lambs)

def generous(lambs):
return int(log2(lambs + 1))

def stingy(lambs):
for henchmen, total_pay in enumerate(accumulate(fibonacci())):
if total_pay > lambs:
return henchmen

def fibonacci():
a, b = 1, 1
while True:
yield a
a, b = b, a + b

• +1 I took too long to write my answer, you've said what I was going to say. Also I like the irony that stingy produces more than generous. Commented Sep 2, 2017 at 20:34
• I don't think that generous() is simply a base-2 logarithm. For example, your generous(13) returns 3, from 1+2+4. This leaves 6 leftover lambs, which is enough to pay a fourth henchman. By the rules of the game, we must do so. We should have generous(13)=4. Commented Nov 13, 2021 at 0:37
• @awwalker Yes, this is possible to pay the fourth henchman using only 6 lambs, but this is not being as generous as possible. If I'm being generous and want to hire a fourth henchman I need to pay them 8 lambs, hence I need at least 15. Commented Nov 14, 2021 at 1:22
• @301_Moved_Permanently The question asks for "the difference between the minimum and maximum number of henchmen who can share the LAMBs... while still obeying all of the above rules to avoid a revolt." When you have 13 LAMBs, you can allocate them among 4 henchmen (e.g. 1+2+4+6) or among 5 henchmen (e.g. 1+1+2+3+5). Any allocation to 3 henchman breaks rule 4 and would cause a revolt. The parenthetical "(that is, being as generous as possible to those you pay and as stingy as possible, respectively)" does not give us carte blanche to ignore rule 4. Commented Nov 15, 2021 at 17:01