Program for minimum number of jumps to reach the end
In this article, we will discuss a program that finds the minimum number of jumps required to reach the end of an array.
Problem Statement
Given an array of non-negative integers, where each element represents the maximum number of steps that can be jumped going forward from that element, we need to find the minimum number of jumps required to reach the end of the array.
Approach and Algorithm
To solve this problem, we can use a dynamic programming approach. The idea is to start from the first element and keep track of the minimum number of jumps required to reach each element.
Let's define an array called 'jump' to store the minimum jumps required to reach each element. We initialize all elements of 'jump' with a maximum value, except the first element which is set to 0.
We then iterate through the array from the second element onwards. For each element, we check all the previous elements and update the minimum jump if the current element can be reached from the previous element in one jump.
To check if the current element can be reached from the previous element, we compare the sum of the previous element's index and its value with the current element's index. If the sum is greater than or equal to the current element's index, it means we can reach the current element in one jump from the previous element.
We update the minimum jump if the total number of jumps required to reach the current element from the previous element is less than the current minimum jump. Finally, we return the minimum jump required to reach the last element of the array.
Below is the pseudocode for the algorithm:
function minimumJumpsToEnd(arr[], n):
if n <= 1:
return 0
if arr[0] == 0:
return -1
jump[n]
jump[0] = 0
for i = 1 to n:
jump[i] = INT_MAX
for j = 0 to i:
if i <= j + arr[j] and jump[j] != INT_MAX:
if jump[i] > jump[j] + 1:
jump[i] = jump[j] + 1
j = i
return jump[n - 1]
Code Solution
/*
C program for
Program for minimum number of jumps to reach the end
*/
#include <stdio.h>
#include <limits.h>
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
int minimumJumpsToEnd(int arr[], int n)
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
int jump[n];
// Initial value
jump[0] = 0;
// Execute loop through by size of n
for (int i = 1; i < n; ++i)
{
// Set initial steps jump
jump[i] = INT_MAX;
// Inner loop which is finding minimum jump between 0 to i
for (int j = 0; j < i; ++j)
{
if (i <= j + arr[j] && jump[j] != INT_MAX)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
}
}
// When jump[ n-1] is INT_MAX
// That means we not reach the end of array elements
return jump[n - 1];
}
void displayArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
int main(int argc, char const *argv[])
{
int arr1[] = {
2 , 1 , 3 , 2 , 3 , 1 , 6 , 7 , 8 , 4 , 2 , 9
};
int arr2[] = {
2 , 3 , 0 , 1 , 2 , 3 , 0 , 1 , 2 , 6 , 4
};
// Test A
int n = sizeof(arr1) / sizeof(arr1[0]);
displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 -> 3 -> 1 -> 6 -> 9
// Jump between ① ② ③ ④
// Ans : 4
printf(" Minimum Jump to end : %d\n", minimumJumpsToEnd(arr1, n));
// Test B
n = sizeof(arr2) / sizeof(arr2[0]);
displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 -> 3 -> 2 -> 3 -> 2 -> 4
// Jump between ① ② ③ ④ ⑤
printf(" Minimum Jump to end : %d\n", minimumJumpsToEnd(arr2, n));
return 0;
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
// Java Program
// Program for minimum number of jumps to reach the end
public class Jumping
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
public int minimumJumpsToEnd(int[] arr, int n)
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
int[] jump = new int[n];
// Initial value
jump[0] = 0;
// Execute loop through by size of n
for (int i = 1; i < n; ++i)
{
// Set initial steps jump
jump[i] = Integer.MAX_VALUE;
// Inner loop which is finding minimum jump between 0 to i
for (int j = 0; j < i; ++j)
{
if (i <= j + arr[j] && jump[j] != Integer.MAX_VALUE)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
}
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1];
}
public void displayArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i] );
}
System.out.print("\n");
}
public static void main(String args[])
{
Jumping task = new Jumping();
int[] arr1 = {
2 , 1 , 3 , 2 , 3 , 1 , 6 , 7 , 8 , 4 , 2 , 9
};
int[] arr2 = {
2 , 3 , 0 , 1 , 2 , 3 , 0 , 1 , 2 , 6 , 4
};
// Test A
int n = arr1.length;
task.displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
System.out.println(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr1, n) );
// Test B
n = arr2.length;
task.displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
System.out.println(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr2, n) );
}
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
// C++ Program
// Program for minimum number of jumps to reach the end
class Jumping
{
public:
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
int minimumJumpsToEnd(int arr[], int n)
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
int jump[n];
// Initial value
jump[0] = 0;
// Execute loop through by size of n
for (int i = 1; i < n; ++i)
{
// Set initial steps jump
jump[i] = INT_MAX;
// Inner loop which is finding minimum jump between 0 to i
for (int j = 0; j < i; ++j)
{
if (i <= j + arr[j] && jump[j] != INT_MAX)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
}
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1];
}
void displayArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
};
int main()
{
Jumping *task = new Jumping();
int arr1[] = {
2 , 1 , 3 , 2 , 3 , 1 , 6 , 7 , 8 , 4 , 2 , 9
};
int arr2[] = {
2 , 3 , 0 , 1 , 2 , 3 , 0 , 1 , 2 , 6 , 4
};
// Test A
int n = sizeof(arr1) / sizeof(arr1[0]);
task->displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
cout << " Minimum Jump to end : " << task->minimumJumpsToEnd(arr1, n) << endl;
// Test B
n = sizeof(arr2) / sizeof(arr2[0]);
task->displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
cout << " Minimum Jump to end : " << task->minimumJumpsToEnd(arr2, n) << endl;
return 0;
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
// Include namespace system
using System;
// Csharp Program
// Program for minimum number of jumps to reach the end
public class Jumping
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
public int minimumJumpsToEnd(int[] arr, int n)
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
int[] jump = new int[n];
// Initial value
jump[0] = 0;
// Execute loop through by size of n
for (int i = 1; i < n; ++i)
{
// Set initial steps jump
jump[i] = int.MaxValue;
// Inner loop which is finding minimum jump between 0 to i
for (int j = 0; j < i; ++j)
{
if (i <= j + arr[j] && jump[j] != int.MaxValue)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
}
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1];
}
public void displayArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args)
{
Jumping task = new Jumping();
int[] arr1 = {
2 , 1 , 3 , 2 , 3 , 1 , 6 , 7 , 8 , 4 , 2 , 9
};
int[] arr2 = {
2 , 3 , 0 , 1 , 2 , 3 , 0 , 1 , 2 , 6 , 4
};
// Test A
int n = arr1.Length;
task.displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
Console.WriteLine(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr1, n));
// Test B
n = arr2.Length;
task.displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
Console.WriteLine(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr2, n));
}
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
package main
import "math"
import "fmt"
// Go Program
// Program for minimum number of jumps to reach the end
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
func minimumJumpsToEnd(arr[] int, n int) int {
if n <= 1 {
// When less than 2 elements
return 0
}
if arr[0] == 0 {
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1
}
// Use to collect number of jump process
var jump = make([]int,n)
// Execute loop through by size of n
for i := 1 ; i < n ; i++ {
// Set initial steps jump
jump[i] = math.MaxInt64
// Inner loop which is finding minimum jump between 0 to i
for j := 0 ; j < i ; j++ {
if i <= j + arr[j] && jump[j] != math.MaxInt64 {
if jump[i] > (jump[j] + 1) {
// Update new minimum jump
jump[i] = jump[j] + 1
}
// Stop inner loop execution
j = i
}
}
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1]
}
func displayArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func main() {
var arr1 = [] int {2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 }
var arr2 = [] int { 2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4 }
// Test A
var n int = len(arr1)
displayArray(arr1, n)
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
fmt.Println(" Minimum Jump to end : ", minimumJumpsToEnd(arr1, n))
// Test B
n = len(arr2)
displayArray(arr2, n)
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
fmt.Println(" Minimum Jump to end : ", minimumJumpsToEnd(arr2, n))
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
<?php
// Php Program
// Program for minimum number of jumps to reach the end
class Jumping
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
public function minimumJumpsToEnd($arr, $n)
{
if ($n <= 1)
{
// When less than 2 elements
return 0;
}
if ($arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
$jump = array_fill(0, $n, 0);
// Execute loop through by size of n
for ($i = 1; $i < $n; ++$i)
{
// Set initial steps jump
$jump[$i] = PHP_INT_MAX;
// Inner loop which is finding minimum jump between 0 to i
for ($j = 0; $j < $i; ++$j)
{
if ($i <= $j + $arr[$j] && $jump[$j] != PHP_INT_MAX)
{
if ($jump[$i] > ($jump[$j] + 1))
{
// Update new minimum jump
$jump[$i] = $jump[$j] + 1;
}
// Stop inner loop execution
$j = $i;
}
}
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return $jump[$n - 1];
}
public function displayArray($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
echo("\n");
}
}
function main()
{
$task = new Jumping();
$arr1 = array(2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9);
$arr2 = array(2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4);
// Test A
$n = count($arr1);
$task->displayArray($arr1, $n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
echo(" Minimum Jump to end : ".
$task->minimumJumpsToEnd($arr1, $n).
"\n");
// Test B
$n = count($arr2);
$task->displayArray($arr2, $n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
echo(" Minimum Jump to end : ".
$task->minimumJumpsToEnd($arr2, $n).
"\n");
}
main();
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
// Node JS Program
// Program for minimum number of jumps to reach the end
class Jumping
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
minimumJumpsToEnd(arr, n)
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
var jump = Array(n).fill(0);
// Execute loop through by size of n
for (var i = 1; i < n; ++i)
{
// Set initial steps jump
jump[i] = Number.MAX_VALUE;
// Inner loop which is finding minimum jump between 0 to i
for (var j = 0; j < i; ++j)
{
if (i <= j + arr[j] && jump[j] != Number.MAX_VALUE)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
}
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1];
}
displayArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
function main()
{
var task = new Jumping();
var arr1 = [2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9];
var arr2 = [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4];
// Test A
var n = arr1.length;
task.displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
console.log(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr1, n));
// Test B
n = arr2.length;
task.displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
console.log(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr2, n));
}
main();
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
import sys
# Python 3 Program
# Program for minimum number of jumps to reach the end
class Jumping :
# This is finding the number of minimum steps
# or jumps required to reach end of list elements
# When of list not contains negative values
def minimumJumpsToEnd(self, arr, n) :
if (n <= 1) :
# When less than 2 elements
return 0
if (arr[0] == 0) :
# When first element is 0 then not possible to
# Visit next element
# Therefor
return -1
# Use to collect number of jump process
jump = [0] * (n)
i = 1
# Execute loop through by size of n
while (i < n) :
# Set initial steps jump
jump[i] = sys.maxsize
j = 0
# Inner loop which is finding minimum jump between 0 to i
while (j < i) :
if (i <= j + arr[j] and jump[j] != sys.maxsize) :
if (jump[i] > (jump[j] + 1)) :
# Update new minimum jump
jump[i] = jump[j] + 1
# Stop inner loop execution
j = i
j += 1
i += 1
# When jump[ n-1] is MAX Integer
# That means we not reach the end of list elements
return jump[n - 1]
def displayArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
def main() :
task = Jumping()
arr1 = [2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9]
arr2 = [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
# Test A
n = len(arr1)
task.displayArray(arr1, n)
# Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
# Jump start with 2 → 3 → 1 → 6 → 9
# Jump between ① ② ③ ④
# Ans : 4
print(" Minimum Jump to end : ",
task.minimumJumpsToEnd(arr1, n))
# Test B
n = len(arr2)
task.displayArray(arr2, n)
# Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
# Jump start with 2 → 3 → 2 → 3 → 2 → 4
# Jump between ① ② ③ ④ ⑤
print(" Minimum Jump to end : ",
task.minimumJumpsToEnd(arr2, n))
if __name__ == "__main__": main()
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
# Ruby Program
# Program for minimum number of jumps to reach the end
class Jumping
# This is finding the number of minimum steps
# or jumps required to reach end of array elements
# When of array not contains negative values
def minimumJumpsToEnd(arr, n)
if (n <= 1)
# When less than 2 elements
return 0
end
if (arr[0] == 0)
# When first element is 0 then not possible to
# Visit next element
# Therefor
return -1
end
# Use to collect number of jump process
jump = Array.new(n) {0}
i = 1
# Execute loop through by size of n
while (i < n)
# Set initial steps jump
jump[i] = (2 ** (0. size * 8 - 2))
j = 0
# Inner loop which is finding minimum jump between 0 to i
while (j < i)
if (i <= j + arr[j] && jump[j] != (2 ** (0. size * 8 - 2)))
if (jump[i] > (jump[j] + 1))
# Update new minimum jump
jump[i] = jump[j] + 1
end
# Stop inner loop execution
j = i
end
j += 1
end
i += 1
end
# When jump[ n-1] is MAX Integer
# That means we not reach the end of array elements
return jump[n - 1]
end
def displayArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
task = Jumping.new()
arr1 = [2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9]
arr2 = [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
# Test A
n = arr1.length
task.displayArray(arr1, n)
# Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
# Jump start with 2 → 3 → 1 → 6 → 9
# Jump between ① ② ③ ④
# Ans : 4
print(" Minimum Jump to end : ",
task.minimumJumpsToEnd(arr1, n), "\n")
# Test B
n = arr2.length
task.displayArray(arr2, n)
# Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
# Jump start with 2 → 3 → 2 → 3 → 2 → 4
# Jump between ① ② ③ ④ ⑤
print(" Minimum Jump to end : ",
task.minimumJumpsToEnd(arr2, n), "\n")
end
main()
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
// Scala Program
// Program for minimum number of jumps to reach the end
class Jumping()
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
def minimumJumpsToEnd(arr: Array[Int], n: Int): Int = {
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr(0) == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
var jump: Array[Int] = Array.fill[Int](n)(0);
var i: Int = 1;
// Execute loop through by size of n
while (i < n)
{
// Set initial steps jump
jump(i) = Int.MaxValue;
var j: Int = 0;
// Inner loop which is finding minimum jump between 0 to i
while (j < i)
{
if (i <= j + arr(j) && jump(j) != Int.MaxValue)
{
if (jump(i) > (jump(j) + 1))
{
// Update new minimum jump
jump(i) = jump(j) + 1;
}
// Stop inner loop execution
j = i;
}
j += 1;
}
i += 1;
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump(n - 1);
}
def displayArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Jumping = new Jumping();
var arr1: Array[Int] = Array(2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9);
var arr2: Array[Int] = Array(2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4);
// Test A
var n: Int = arr1.length;
task.displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
println(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr1, n));
// Test B
n = arr2.length;
task.displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
println(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr2, n));
}
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
import Foundation;
// Swift 4 Program
// Program for minimum number of jumps to reach the end
class Jumping
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
func minimumJumpsToEnd(_ arr: [Int], _ n: Int) -> Int
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
var jump: [Int] = Array(repeating: 0, count: n);
var i: Int = 1;
// Execute loop through by size of n
while (i < n)
{
// Set initial steps jump
jump[i] = Int.max;
var j: Int = 0;
// Inner loop which is finding minimum jump between 0 to i
while (j < i)
{
if (i <= j + arr[j] && jump[j] != Int.max)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
j += 1;
}
i += 1;
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1];
}
func displayArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
func main()
{
let task: Jumping = Jumping();
let arr1: [Int] = [2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9];
let arr2: [Int] = [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4];
// Test A
var n: Int = arr1.count;
task.displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
print(" Minimum Jump to end : ", task.minimumJumpsToEnd(arr1, n));
// Test B
n = arr2.count;
task.displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
print(" Minimum Jump to end : ", task.minimumJumpsToEnd(arr2, n));
}
main();
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
// Kotlin Program
// Program for minimum number of jumps to reach the end
class Jumping
{
// This is finding the number of minimum steps
// or jumps required to reach end of array elements
// When of array not contains negative values
fun minimumJumpsToEnd(arr: Array < Int > , n: Int): Int
{
if (n <= 1)
{
// When less than 2 elements
return 0;
}
if (arr[0] == 0)
{
// When first element is 0 then not possible to
// Visit next element
// Therefor
return -1;
}
// Use to collect number of jump process
var jump: Array < Int > = Array(n)
{
0
};
var i: Int = 1;
// Execute loop through by size of n
while (i < n)
{
// Set initial steps jump
jump[i] = Int.MAX_VALUE;
var j: Int = 0;
// Inner loop which is finding minimum jump between 0 to i
while (j < i)
{
if (i <= j + arr[j] && jump[j] != Int.MAX_VALUE)
{
if (jump[i] > (jump[j] + 1))
{
// Update new minimum jump
jump[i] = jump[j] + 1;
}
// Stop inner loop execution
j = i;
}
j += 1;
}
i += 1;
}
// When jump[ n-1] is MAX Integer
// That means we not reach the end of array elements
return jump[n - 1];
}
fun displayArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Jumping = Jumping();
val arr1: Array < Int > = arrayOf(2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9);
val arr2: Array < Int > = arrayOf(2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4);
// Test A
var n: Int = arr1.count();
task.displayArray(arr1, n);
// Given [2, 1, 3, 2, 3, 1 , 6, 7, 8, 4, 2, 9 ]
// Jump start with 2 → 3 → 1 → 6 → 9
// Jump between ① ② ③ ④
// Ans : 4
println(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr1, n));
// Test B
n = arr2.count();
task.displayArray(arr2, n);
// Given [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
// Jump start with 2 → 3 → 2 → 3 → 2 → 4
// Jump between ① ② ③ ④ ⑤
println(" Minimum Jump to end : " +
task.minimumJumpsToEnd(arr2, n));
}
Output
2 1 3 2 3 1 6 7 8 4 2 9
Minimum Jump to end : 4
2 3 0 1 2 3 0 1 2 6 4
Minimum Jump to end : 5
Example and Output
Let's consider two examples to demonstrate the program.
Example A:
Array: [2, 1, 3, 2, 3, 1, 6, 7, 8, 4, 2, 9]
The minimum number of jumps required to reach the end is 4.
Explanation: We can jump from index 0 to index 2, then to index 5, then to index 6, and finally to index 11.
Example B:
Array: [2, 3, 0, 1, 2, 3, 0, 1, 2, 6, 4]
The minimum number of jumps required to reach the end is 5.
Explanation: We can jump from index 0 to index 1, then to index 4, then to index 7, then to index 9, and finally to index 10.
Time Complexity: The time complexity of this algorithm is O(n^2) because of the nested loop. The outer loop runs n times, and the inner loop runs up to i times for each i. However, this can be optimized to O(n) using a different approach, which is beyond the scope of this article.
Finally
In this article, we discussed a program to find the minimum number of jumps required to reach the end of an array. We explained the problem statement, provided a step-by-step algorithm with pseudocode, and demonstrated the program with examples. The code implementation and time complexity analysis were also covered.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment