10. Minimum jumps to reach the end.

10. Minimum jumps to reach the end.

Problem link :- click here

C code

//min jumps to end
#include<stdio.h>

int max(int a, int b)
{
    if(a>b)
        return a;
    return b;
}

int min_jump(int a[], int n)
{
    int i, step, max_range, jump;

    if(n <= 1)
        return 0;
    if(a[0] == 0)
        return -1;

    jump = 1;
    step = a[0];
    max_range = a[0];    //maximum reachable index

    for(i=1; i<n; i++)
    {
        if(i == n-1)
            return jump;

        max_range = max(max_range, i+a[i]);
        step--;
        if(step == 0)
        {
            jump++;
            if(i>=max_range)
                return -1;
            if(max_range >= n-1)
                return jump;
            step = max_range - i;
        }
    }
    return jump;
}


void main()
{
    int arr[30];
    int i, n, ans;

    printf("Enter the size of the array\n");
    scanf("%d",&n);
    printf("Enter the elements of the array\n");
    for(i=0; i<n; i++)
        scanf("%d",&arr[i]);

    printf("Given Array\n");
    for(i=0; i<n; i++)
        printf("\t%d",arr[i]);
    printf("\n");

    ans = min_jump(arr, n);
    printf("\n\nMinimum jumps possible to end of the array is %d\n\n",ans);
}

Java code

//Minimum jumps to reach end
package programs;

import java.util.*;

public class Array__10
{

	static int max(int a, int b)
	{
		if(a > b)
			return a;
		return b;
	}
	
	static int min_jumps(int arr[], int n)
	{
		int jumps, steps, max_range;
		
		if(n<=1)
			return 0;
		if(arr[0] == 0)
			return -1;
		
		jumps = 1;
		steps = arr[0];
		max_range = arr[0];
		for(int i=1; i<n; i++)
		{
			if(i==n-1)
				return jumps;
			
			max_range = max(max_range, i+arr[i]);
			steps--;
			if(steps == 0)
			{
				jumps++;
				if(i>=max_range)
					return -1;
				if(max_range >= n-1)
					return jumps;
				steps = max_range - i;
			}
		}
		return jumps;
	}
	
	public static void main(String[] args)
	{
		int array[] = new int[20];
		int n, i, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array :");
		n = s.nextInt();
		System.out.println("Enter the elements of the array :");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.println("Given Array :");
		print_array(array, n);
		
		ans = min_jumps(array, n);
		System.out.println("\n\nMinimum jumps to reach the end of the array is " + ans);

	}

	static void print_array(int arr[], int n)
	{
		for(int i=0; i<n; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)