Minimum Jumps to Reach Home - Practice Coding Problems

Minimum Jumps to Reach Home - Problem

A bug starts at position 0 on the x-axis and wants to reach its home at position x.

The bug can move according to these rules:

Jump exactly a positions forward (to the right)
Jump exactly b positions backward (to the left)
Cannot jump backward twice in a row
Cannot jump to any forbidden positions
Cannot jump to negative positions

The bug may jump forward beyond its home, but it cannot go to negative positions.

Given an array forbidden where forbidden[i] means the bug cannot jump to position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home at position x. If impossible, return -1.

Input & Output

Example 1 — Basic Case

$ Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9

› Output: 3

💡 Note: Bug jumps: 0 → 3 → 6 → 9. Three forward jumps of size 3 each reach position 9.

Example 2 — Impossible Case

$ Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11

› Output: -1

💡 Note: Position 11 cannot be reached due to forbidden positions and jump constraints.

Example 3 — Single Jump

$ Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7

› Output: 2

💡 Note: Bug can jump: 0 → 16 → 7 (forward jump to 16, then backward jump to 7).

Constraints

1 ≤ forbidden.length ≤ 1000
1 ≤ a, b, forbidden[i] ≤ 2000
0 ≤ x ≤ 2000
All values in forbidden are distinct
Position x is not forbidden

Visualization

Tap to expand

Understanding the Visualization

Input

forbidden=[14,4,18,1,15], a=3, b=15, x=9

Process

Find shortest path using BFS with state tracking

Output

Minimum 3 jumps: 0→3→6→9

Key Takeaway

🎯 Key Insight: Use BFS with state tracking to handle the consecutive backward jump constraint efficiently

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use BFS while tracking both position and last move direction to enforce the consecutive backward jump rule. The optimal approach uses BFS with state (position, last_backward_flag) and bounds checking to find minimum jumps. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2^n)	O(n)	Try all possible jump sequences using recursion with memoization
Breadth-First Search	O(n)	O(n)	Use BFS to find shortest path by exploring positions level by level

Recursive Backtracking — Algorithm Steps

Start from position 0
For each position, try forward jump (+a) and backward jump (-b) if valid
Track last move direction to prevent consecutive backward jumps
Return minimum jumps to reach target

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at 0

Begin at position 0 with 0 jumps

Try Moves

At each position, try forward (+a) and backward (-b) if valid

Track State

Remember if last move was backward to prevent consecutive backward jumps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_POS 6001
#define MAX_FORBIDDEN 1000

int forbiddenSet[MAX_POS];
int memo[MAX_POS][2];
int A, B, X;

int dfs(int pos, int lastBackward, int jumps) {
    if (pos == X) return jumps;
    if (pos < 0 || pos >= MAX_POS || forbiddenSet[pos]) return INT_MAX;
    if (memo[pos][lastBackward] != -1) return memo[pos][lastBackward];
    
    int result = INT_MAX;
    // Forward jump
    if (pos + A < MAX_POS) {
        int forward = dfs(pos + A, 0, jumps + 1);
        if (forward != INT_MAX && forward < result) result = forward;
    }
    
    // Backward jump
    if (!lastBackward && pos - B >= 0) {
        int backward = dfs(pos - B, 1, jumps + 1);
        if (backward != INT_MAX && backward < result) result = backward;
    }
    
    memo[pos][lastBackward] = result;
    return result;
}

int solution(int* forbidden, int forbiddenSize, int a, int b, int x) {
    memset(forbiddenSet, 0, sizeof(forbiddenSet));
    memset(memo, -1, sizeof(memo));
    
    for (int i = 0; i < forbiddenSize; i++) {
        if (forbidden[i] < MAX_POS) forbiddenSet[forbidden[i]] = 1;
    }
    A = a; B = b; X = x;
    
    int result = dfs(0, 0, 0);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int forbidden[MAX_FORBIDDEN];
    int forbiddenSize = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && forbiddenSize < MAX_FORBIDDEN) {
            forbidden[forbiddenSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);
    
    printf("%d\n", solution(forbidden, forbiddenSize, a, b, x));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can branch into 2 moves, leading to exponential exploration

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and memoization table for visited states

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler