I’ve recently decided to learn Python, which means that I’ve been Googling a lot of simple search terms to learn command syntax. One of these searches led to an invitation to foobar, an online coding challenge run by Google. This post concerns one of the early problems in Google foobar, lovely-lucky-lambs.

I wouldn’t usually comment on a problem like this, but the accepted answer for the lovely-lucky-lambs problem is false. This doesn’t seem to be acknowledged anywhere, which is strange given the reach/duration of foobar (and Cunningham’s Law). In this post, I’ll introduce the lovely-lucky-lambs problem and discuss why the official test case answers are sometimes incorrect. This post contains major spoilers, so be warned.

Here is the lovely-lucky-lambs problem, in its entirety:

Lovely Lucky LAMBs

==================
Being a henchman isn’t all drudgery. Occasionally, when feeling generous, Commander Lambda 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 solution(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, solution(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 a positive integer less than 1 billion (10 ^ 9).

In summary, we have some number of LAMBs to distribute and rules which govern their distribution. We’d like to know the difference between the most number of recipients and the fewest, subject to those rules.

Rules (1) and (3) imply that the nth recipient (in order of increasing seniority) must receive at least LAMBs, where is the nth Fibonacci number (indexed starting at ). Let denote the sum of the first Fibonacci numbers. Then any distribution of LAMBs to henchmen requires at least LAMBs; in other words, if we have fewer than LAMBs, we must allocate LAMBs to fewer than henchmen.

Thus an upper bound for the number of recipients is the largest for which . This upper bound is clearly sharp. It’s also easy to compute:

def most_recipients(n):
    recipients = 0
    partial_sum = 0
    while partial_sum <= n:
        recipients += 1
        partial_sum = partial_sum + fibonacci(recipients)
    return recipients -1

Here, fibonacci(n) returns the nth Fibonacci number. I won’t include code for it so I don’t get yelled at for implementing the recursion inefficiently. This code overcounts and then corrects by 1. As an exercise, we can prove that and implement most_recipients() that way. This wouldn’t do much to speed up the code, though.

The lower bound for the number of recipients is more nuanced. Rules (1) and (2) imply that the nth henchman may receive no more than LAMBs. This implies that the total number of LAMBs awarded to henchman is at most . Conversely, any distribution of more than LAMBs requires at least recipients. This lower bound for recipients is also easy to code:

def lower_bound_recipients(n):
    import math
    return int(math.floor(math.log(n+1,2)))

This function returns the maximal for which the sum remains less than or equal to . In particular, with this distribution scheme, it is not possible to add another henchman at the top of seniority and pay them twice the rate of the previous henchman. Thus the lower bound is optimal, correct?

Yes and no. It’s true that defining

def solution(n):
    return most_recipients(n) - lower_bound_recipients(n)

passes the ten predetermined “random” test cases for the lovely-lucky-lambs challenge. (Note: I suspect that the test cases are determined once and fixed for all users, but I am not 100% certain. More on this later.)

When we get into the weeds of things, though, we see that lower_bound_recipients() need not be optimal. In fact, it breaks as early as . For , we compute a lower bound of 1 recipient, since is already too large. However, the solution which allocates one LAMB to a first henchman and pockets the rest is not a valid distribution scheme: it violates rule (4), which states that we must give the remaining LAMB to a second 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.

Thus any allocation of two LAMBs must go to exactly two henchmen, and the lower bound is incorrect.

There is an easy fix: we simply compute the maximal number of henchman who can be paid in geometric progression, and then check if the surplus LAMBs are enough to demand we hire another henchman. Here is one version of the corrected lower bound:

def fewest_recipients(n):
    recipients = 0
    partial_sum = 0
    # Overcount the geometric progression by 1
    while partial_sum <= n:
        partial_sum = partial_sum + 2 ** recipients
        recipients += 1
    # Correct for the overcount:
    recipients -= 1
    partial_sum = partial_sum - 2 ** recipients

    gap = n - partial_sum

    if recipients >= 2 and gap >= 2 ** (recipients -1) + 2 ** (recipients -2):
        return recipients + 1
    elif recipients == 1 and gap >= 2 ** (recipients -1):
        return recipients + 1
    else:
        return recipients

This disagrees with the previous lower bound for . For , they disagree on the union of the intervals .

To investigate whether or not this nuance could be responsible for my test case failures, I modified my code to probe the black box test cases. Since solution() defined above passed all the test cases, a version like

def solution(n):
    if n < M:
        return most_recipients(n) - lower_bound_recipients(n)
    else:
        return -1

would pass exactly those test cases with . If we don’t value our time, we can manually binary search up to 10^9 to determine the exact used in the test cases. For me, the test cases were

(Disclaimer: I don’t know if these test cases are universal, but I expect that they are. They appear to be chosen specifically to test edge cases. For example, 75024 is the sum of the first 23 Fibonacci numbers.)

The “corrected” code fails two test cases: and . For , we’ve already mentioned that any distribution of 2 LAMBs must go to two henchman, so the difference between the most and fewest recipients should be 0. The accepted answer is 1, which is incorrect.

The second failed test case is . Here, the accepted solution is 9 and my proposed correction is 8. The maximum number of recipients is 28 (since ). For the minimal number of recipients, we note that . This gives a lower bound of 19 recipients. However, even in this extremal case (in which each henchman is paid maximally), there remains enough leftover LAMB to pay a 20th henchman. We have 393216 remaining LAMB, which exactly equals . Thus a 20th henchman would need to be added, per rule (4). (Note that a 20th henchman is barely avoided in test case 8.)

Some concluding remarks:

1. The four rules which restrict LAMB allocation were carefully chosen to produce our upper and lower bounds. Rules (1) and (3) give a lower bound for LAMBs and thus an upper bound for recipients. Rules (1) and (2) give the upper bound for payouts. Some version of rule (4) was needed so that the lower bound for recipients wasn’t 0 (keeping all the LAMBs for oneself). The specific wording of rule (4) seems to have been misinterpreted by whoever coded the internal version of solution().
2. The test cases 917502 and 917503 seem specifically designed to test the precise interpretation of rule (4). I suspect that the test cases and internal solution were written by different people.
3. This issue with lovely-lucky-lambs is alluded to in a Stack Overflow post here. The original submission attempts to implement rule (4) correctly, but makes an error along the way (and ironically passes the test case by accident). A proposed solution passes all test cases by incorrectly implementing rule (4). The potential issue with is noted in a comment, but the veracity of the accepted answers is not discussed.