Jump Game Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Jump Game Reachability Check

What is the output of the following C code that checks if you can reach the last index of the array?

DSA C

int canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

int main() {
    int arr[] = {2,3,1,1,4};
    int size = sizeof(arr)/sizeof(arr[0]);
    int result = canJump(arr, size);
    printf("%d\n", result);
    return 0;
}

A 0

B 1

C Compilation error

D Runtime error

💡 Hint

Think about whether the maximum reachable index covers the last index.

The function tracks the furthest index reachable. Since the array allows jumps to reach the end, the function returns 1.

❓ Predict Output

intermediate

Output when jump is not possible

What will be printed by this C program that uses the jump game logic?

DSA C

int canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

int main() {
    int arr[] = {3,2,1,0,4};
    int size = sizeof(arr)/sizeof(arr[0]);
    int result = canJump(arr, size);
    printf("%d\n", result);
    return 0;
}

A 1

B Compilation error

C 0

D Segmentation fault

💡 Hint

Check if the zero in the array blocks progress.

The zero at index 3 blocks further jumps, so the last index is unreachable, returning 0.

🧠 Conceptual

advanced

Understanding the Greedy Approach in Jump Game

Why does the greedy approach work for the Jump Game problem instead of trying all possible jumps?

A Because it uses dynamic programming to store all reachable indices.

B Because it tries every possible jump recursively to find the path.

C Because it sorts the array to find the best jumps first.

D Because the maximum reachable index always increases or stays the same, ensuring no need to backtrack.

💡 Hint

Think about how the maximum reachable index changes as you move forward.

The greedy approach works because it keeps track of the furthest reachable index and never needs to revisit previous positions.

❓ Predict Output

advanced

Output of Jump Game with Zero at Start

What will the following C program print when the first element is zero?

DSA C

int canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

int main() {
    int arr[] = {0,2,3};
    int size = sizeof(arr)/sizeof(arr[0]);
    int result = canJump(arr, size);
    printf("%d\n", result);
    return 0;
}

A 0

B 1

C Runtime error

D Compilation error

💡 Hint

If the first jump length is zero, can you move forward?

Since the first element is zero, you cannot move anywhere, so the last index is unreachable.

🧠 Conceptual

expert

Time Complexity of Jump Game Greedy Solution

What is the time complexity of the greedy solution for the Jump Game problem and why?

A O(n), because it scans the array once updating the maximum reachable index.

B O(n^2), because it checks all jumps from each index.

C O(log n), because it uses binary search to find jumps.

D O(1), because it uses constant time operations.

💡 Hint

Consider how many times the loop runs and what operations it performs inside.

The greedy solution runs in linear time because it iterates through the array once, updating the maximum reachable index without nested loops.