I know I said I would take a break, but I was way too excited after my success on the first challenge to take said break, so I jumped back onto Foobar. I’m no longer on the bottom of the “minion” pile after completing the first challenge, so I’m no longer required to pick up minion poo (I kid you not, somebody is having WAY too much fun writing this stuff at Google). I quickly type in request again and the timer pops up with 72 hours to complete challenge 1 of level 2. Here we go:
The Problem Set-Up
The second problem was slightly more involved than the previous. In this program, the method inputs an integer that represented ” lucky lambs”, a currency Commander Lambda can give to her minions. There are some rules with how lucky lambs got handed out:
- The first minion gets 1 Lamb and there will always be at least one team member.
- The next minion in line cannot be given more than double the amount the previous minion received.
- A minion cannot be given less than the sum for the previous two minions (this rule doesn’t affect the first minion and the second minion only needs to make equal or more than minion 1).
- You must always add better paid minions, as long as you follow the previous rules.
The problem asks what would be the difference in minions that could be paid if you were as generous as possible and as stingy as possible.
For example, suppose you have 10 Lambs. Being as generous as possible you could only pay 3 minions (1+2+4 = 7). If you were as stingy as possible, you could pay 4 minions (1+1+2+3=7). The difference between the most stingy and the most generous is 1 minion.
The Solution Design
This is why paying attention to their test cases is so important! If you look at the most stingy rules (current minion equals the sum of the two previous minions), a famous pattern becomes clear: 1, 1, 2, 3, 5, 8, 13, 21, … The Fibonacci Sequence! The most generous case is also a special sequence: 1, 2, 4, 8, 16, … or a geometric sequence. So find a way to calculate the sum of Fibonacci Numbers, the sum of a geometric sequence, how many numbers are in each sequence, and the difference the numbers in those sequences.
To find the nth number in the Fibonacci sequence, I looped through and incremented. There is a more efficient way that makes the problem constant time, but I only found it after I submitted my code. It uses some interesting properties of the sum of Fibonacci numbers and the Golden Ratio. I highly recommend looking it up. If anyone is interested, we can discuss it in the comments.
You could do a similarly naïve approach to the geometric series, but I remembered from math class that there is a formula to calculate the sum of a geometric series:
Where S is the sum for that many number, r is the rate, and n is the amount of numbers. In our case, r = 2 because each number doubles. So our formula really becomes:
Where we would solve for n.
So we now have our Fibonacci counter and our geometric counter, so we just subtract the two right? Well….not quite. Using our current method something weird would happen if we looked at 13. The stingy scheme would yield 1+1+2+3+5=12 and the generous scheme would yield 1+2+4=7. That would make the difference between the two schemes 2. However, rule 4 of the problem says that we have to add minions if we don’t break any other rule. In this case we can do 1+2+4+6=13 without breaking a rule. 6 is less than or equal to doubling the previous number, and 6 is less than or equal to the sum of the previous two numbers. So the true difference is only 1.
Examples during this challenge are so important! The problem is written as a wall of flavor text, so deciphering meaning is difficult and crucial. Only by paying attention to the examples was it possible to see the two sequences arise.
The other lesson is that running examples by hand can help extract meaning. After choosing a couple of test numbers, actually adding them by hand helps to verify that you’re on the right track.
I verified my code: ALL TEST CASES PASSED! What a relief. I submitted the code with a lot less trepidation than the first time. A bar showed up showing that only 50% of level 2 is complete. Looks like I have another one in the pipeline!