Skip to main content

Program for minimum number of jumps to reach the end

Here given code implementation process.

/*
    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
Last updated on by Kalkicode




Comment

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