how to get to the target floor in minimum time if one can move to N + 1, N - 1 and 2 * N in one minute?

user_12137041 0
Viewed 169

This is a problem I was asked to solve during an interview, but the code I implemented during interview cannot pass all test cases, the problem is just as title said, given N and T (T >= N), which are initial floor and target floor respectively, one can move to current floor + 1, current floor - 1 or 2 * current floor in one minute, what's the minimum time need to reach the target? I think it's a typical DP problem, this is how I did in interview

@lru_cache(None)
def solve(cur):
    if cur >= target: return cur - target
    if cur * 2 >= target:
        # if current floor * 2 < target, we can move to current floor + 1 each time or move backward to (target + 1) // 2 and move current floor * 2 next time, and if target is odd, we need extra 1 move
        return min(target - cur, cur - (target + 1) // 2 + 1 + (target % 2))
    return min(solve(cur + 1), solve(cur * 2)) + 1

I test it with some cases, it seems to work, I cannot figure out why it cannot pass all test cases during interview,

Update---------------------------------------------------------------

I tried using Dijkstra to solve this, but the code become a bit of mess, than I thought if the problem askes to find shortest distance, maybe we can use BFS, and I think it's the right solution, so below is the code

def solve():
    while(True):
        N, T = map(int, input().split())
        q = deque([N])
        vis = [False] * (T * 2)
        vis[N] = True
        steps = 0
        while q:
            for _ in range(len(q)):
                u = q.popleft()
                if u == T:
                    print(f'reach target in {steps} minutes')
                    break
                cand = [u - 1, u + 1, u * 2] if u < T else [u - 1]
                for v in cand:
                    if v > 0 and not vis[v]:
                        vis[v] = True
                        q.append(v)
            steps += 1
dynamic-programming algorithm
2 Answers

An easy way is to start from the target T and to found how many iterations we need to go down to initial value N. Here, the allowed operations are +1, -1 and division by 2.

The key point is that division by 2 is only allowed for even value of T. Moreover, if T is even effectively, then it seems clear that division by 2 is the road to take, except if T is near enough to N. This little issue is solved by comparing 1 + nsteps(N, T/2) with T - N.

If T is odd, we must have to compare nsteps(N, T-1) with nsteps(N, T+1).

Last but not least, if T is less than N, then the number of steps is equal to N - T.

Complexity: ??

Here is a simple C++ implementation to illustrate the algorithm. It should be easy to adapt it in any language.

#include <iostream>
#include <algorithm>

int nsteps (int n, int t) {
    if (t <= n) {
        return n - t;
    }
    if (t%2 == 0) {
        return std::min (1 + nsteps(n, t/2), t-n);
    }
    return 1 + std::min (nsteps(n, t-1), nsteps(n, t+1));
}
    
int main () {
    int n, t;
    std::cin >> n >> t;
    std::cout << nsteps (n, t) << std::endl;
    return 0;
}

In practice, as noted in a comment by @David Eisenstat, it is still slow, at least in some occasions. For example, for an input 1 1431655765, it needs 10891541 calls of the function. I modified the code hereafter, by using the value of T modulo 4 in order to speed it up: if T is large enough, we can decide betweens the two roads when Tis odd. In the same test case, only 46 calls are needed now.

In this case, the complexity seems indeed equal to O(log T).

int cpt2 = 0;
long long int nsteps2 (long long int n, long long int t) {
    cpt2++;
    if (t <= n) {
        return n - t;
    }
    if (t%2 == 0) {
        return std::min (1ll + nsteps2(n, t/2), t-n);
    }
    if (t/4 < n) return 1ll + std::min (nsteps2(n, t-1), nsteps2(n, t+1));
    if (t%4 == 1) return 1ll + nsteps2(n, t-1);
    else return 1ll + nsteps2(n, t+1);
}
user_105533410

As you mentioned, we can make use of normal BFS search for this question as the direction for our movement between floor is given already as floor + 1 or floor - 1 or floor / 2. As per my understanding a floor / 2 movement is only possible if we are at an even floor.

Here is my java code for the same :


int findSteps(int n, int t) {
    if (n > t) {
        return n - t;
    }
    if (n == t) {
        return 0;
    }
    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> visited = new HashSet<>();
    queue.offer(n);
    visited.add(n);
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i=0; i<size; i++) {
            int currentFloor = queue.poll();
            if (currentFloor == t)
                return steps;
            int possibleMove1 = currentFloor + 1;
            int possibleMove2 = currentFloor - 1;
            int possibleMove3 = currentFloor % 2 == 0 ? currentFloor / 2 : -1;
           // out of bound conditions or visited condition 
            if (possibleMove1 < t && possibleMove1 > n && !visited(possibleMove1)) {
                queue.offer(possibleMove1);
                visited.add(possibleMove1);
            }
            if (possibleMove2 < t && possibleMove2 > n && !visited(possibleMove2)) {
                queue.offer(possibleMove2);
                visited.add(possibleMove2);
            }
            if (possibleMove3 < t && possibleMove3 > n && !visited(possibleMove3)) {
                queue.offer(possibleMove1);
                visited.add(possibleMove1);
            }
        }
        steps += 1;
    }
    return -1;
}

Note : There is some repeating codes that can be moved to a separate function and use that function instead.

user_135060010
Related