Race to Finish Line - Google Top Interview Questions

                        Solution in C++ :

int dp[100005];
// dp[i] is the minimum time needed to travel exactly a distance of i

int solve(int target) {
    if (dp[target]) {
        return dp[target];
    }
    int time = 0;
    int speed = 1;
    int position = 0;
    // this is achievable by accelerating, then reversing twice, repeating "target" times until we
    // get to the target
    int besttime = 3 * target;
    while (true) {
        position += speed;
        time++;
        if (position == target) {
            besttime = min(besttime, time);
            break;
        }
        // reverse once, but since we're after the target we don't continue traveling further
        // forward
        if (position > target) {
            besttime = min(besttime, time + 1 + solve(position - target));
            break;
        }
        // reverse twice to reset speed to 1
        besttime = min(besttime, time + 2 + solve(target - position));
        // reverse in the middle, but don't reverse all the way
        if (speed > 1) {
            int candtime = time + 2;
            int candposition = target - position;
            for (int revspeed = 1; candposition + revspeed < target; revspeed *= 2) {
                candposition += revspeed;
                candtime++;
                besttime = min(besttime, candtime + solve(candposition));
            }
        }
        speed *= 2;
    }
    dp[target] = besttime;
    return besttime;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int target) {
        if (target == 0)
            return 0;
        boolean[][] ff = new boolean[38][target * 2 + 1];
        LinkedList<Integer> ll1 = new LinkedList(), ll2 = new LinkedList();
        ll1.add(0);
        ll2.add(0);
        ff[0][0] = true;
        int lay = 0, count = 1;
        while (!ll1.isEmpty()) {
            int p = ll1.poll(), s = ll2.poll();
            int speed = s < 19 ? 1 << s : -(1 << (s - 19));
            if (p + speed == target)
                return lay + 1;
            if (p + speed >= 0 && p + speed < ff[0].length && !ff[s + 1][p + speed]) {
                ll1.add(p + speed);
                ll2.add(s + 1);
                ff[s + 1][p + speed] = true;
            }
            s = s < 19 ? 19 : 0;
            if (!ff[s][p]) {
                ll1.add(p);
                ll2.add(s);
                ff[s][p] = true;
            }
            --count;
            if (count == 0) {
                ++lay;
                count = ll1.size();
            }
        }
        return -1;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, target):
        self.ans = int(1e9)
        hi = 1
        while (1 << hi) < target:
            hi += 1
        self.dfs(hi, 0, 0, 0, target)
        return self.ans

    def dfs(self, digit, cost, pos, neg, target):
        tot = cost + max(2 * (pos - 1), 2 * neg - 1)
        if tot >= self.ans:
            return
        if target == 0:
            self.ans = min(self.ans, tot)
            return
        step = (1 << digit) - 1
        if step * 2 < abs(target):
            return
        self.dfs(digit - 1, cost, pos, neg, target)
        self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
        self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
        self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
        self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)