# Google FooBar Level 3 - Shortest path to 1

I recently found the Google Foobar challenges and am having a problem with level 3. The goal of the task is the find the minimum number of operations needed to transform a group of pellets down into 1, while following these rules:

1) Add one fuel pellet

2) Remove one fuel pellet

3) Divide the entire group of fuel pellets by 2 (due to the destructive energy released when a quantum antimatter pellet is cut in half, the safety controls will only allow this to happen if there is an even number of pellets)

My code is as follows:

from math import log, ceil, floor
steps = 0
steps_taken = " => {}"
all_steps = "{}".format(n)
n = int(n)
if n < 1:
return 0
while n > 1:
if n == 3:
n -= 1
all_steps += steps_taken.format(n)
steps += 1
elif n % 2 == 1:
if n + 1 == 2**closest_power(n+1):
n += 1
all_steps += steps_taken.format(n)
elif n - 1 == 2**closest_power(n-1):
n -= 1
all_steps += steps_taken.format(n)
else:
n -= 1
all_steps += steps_taken.format(n)
steps += 1
else:
n = n / 2
all_steps += steps_taken.format(n)
steps += 1

print all_steps
return steps

def closest_power(x):
possible_results = floor(log(x, 2)), ceil(log(x, 2))
return int(min(possible_results, key= lambda z: abs(x-2**z)))


This manages to perform the two test cases provided:

Inputs:

(string) n = "4"


Output:

(int) 2


Inputs:

(string) n = "15"


Output:

(int) 5


But it fails on others, that Google doesn't make available. Since I don't have access to the failing test cases, I'm looking for performance suggestions.

Right now the code is making the following assumptions:

• If the number is even, divide it by two. This should reduce the amount of space left to reach 1
• If a number is odd, check if the next and previous numbers are a power of 2. If so, add or subtract one to get to that number. Since powers of 2 can be divided repeatedly, there will be no more adding/subtracting of pellets
• If neither neighbor is a power of two, subtract one. I am betting this is the assumption that is causing problems. I don't have the mathematical background to provide it, but my thought was that moving closer to 1 is better.
• If the number is 3, subtract 1. Since both of its neighbors are a power of two, this is a special case. Additionally, moving from 3->2->1 is shorter than 3->4->2->1.

Your intuition is correct. A blind subtraction is the root cause of the problem.

The odd number has the least significant bit equals to 1. An even number has it equal to 0. The more zeroes a number has at the tail, the more divisions you can perform (this is what makes powers of 2 so special - they have all bits but most significant equal to 0). So what you really want is to compute number of trailing 0 bits in n + 1 and n - 1 and pick one which has more:

    tz0 = trailing_zero_bits(n + 1)
tz1 = trailing_zero_bits(n - 1)
if tz0 > tz1:
n = n + 1
else:
n = n - 1


Notice how it eliminates computation of closest power of 2.

I leave the implementation of trailing_zero_bits for you. Hint: it is a one-line bit manipulation.

Edit. I am slow. It only took 6 years to realize that the suggested trailing_zero_bits is an overkill. All you need to do is to test second-to-LSB bit. Indeed, an odd number is either

****01


or

****11


In the first case an increment makes no sense. In the second so does decrement.

• This was very helpful. Thank you for the pointer about trailing zeros. Implementing the trailing_zero_bits check (and removing the closest power of 2 check I was doing) now passes 8 out of 10 of the cases! I'll see if I can figure out these last two cases on my own. It's difficult without actually seeing the data they are testing though. Nov 3, 2016 at 18:32
• @ConfusedintheEast Are they fail with WA or TLE or something else?
– vnp
Nov 3, 2016 at 18:56
• Unfortunately, all it tells me is that the test failed: i.imgur.com/jMFBwXU.png Nov 3, 2016 at 19:31
• This algorithm would seem to be incorrect for n = 3. But it might be correct for n > 3.
– JS1
Nov 5, 2016 at 12:12
• Can we have a solution in java as well? can we simplify the same using bit manipulation when doing in Java? Just curious May 4, 2017 at 20:48