CareerCup

DP solution in C#

onestopinterviewprep.blogspot.com/2014/03/traverse-array-in-shortest-number-of.html

All above solution is non-linear complexity. if the question is only the number of steps then I have O(n) solution. Mine function return -1 if there is no feasible solution

#include <iostream>
#include <vector>

using namespace std;

int minJump(vector<int> jumps)
{
    size_t n = jumps.size();

    bool feasible = true;
    size_t lend = 1;
    int jump_cnt = 1;
    int i = 0;

    while (feasible)
    {
        size_t lr = 0;
        for ( ; i < lend; ++i)
            if (i + jumps[i] > lr)
                lr = i + jumps[i] + 1;
        if (lr >= n)
            break;
        feasible = (lend < lr);
        lend = lr;
        ++jump_cnt;
    }
    return feasible ? jump_cnt : -1;
}

int main()
{
    //int a[] = {1, 5, 4, 6, 9, 3, 0, 0, 1, 3};
    int a[] = {2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
    std::vector<int> va(a, a + sizeof(a) / sizeof(a[0]));
    std::cerr << minJump(va);

}

// Returns minimum number of jumps to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
    int *jumps = new int[n];  // jumps[n-1] will hold the result
    int i, j;
 
    if (n == 0 || arr[0] == 0)
        return INT_MAX;
 
    jumps[0] = 0;
 
    // Find the minimum number of jumps to reach arr[i]
    // from arr[0], and assign this value to jumps[i]
    for (i = 1; i < n; i++)
    {
        jumps[i] = INT_MAX;
        for (j = 0; j < i; j++)
        {
            if (i <= j + arr[j] && jumps[j] != INT_MAX)
            {
                 jumps[i] = jumps[j] + 1;
                 break;
            }
        }
    }
    return jumps[n-1];
}

Here is a DP solution in C#.
Time complexity is O(N). Each index is evaluated only once. You can see it by looking at the print traces.

private static Hashtable cachedResults = new Hashtable();

        private static int CacheAndReturn(int index, int jump)
        {
            cachedResults.Add(index, jump);
            return jump;
        }

        private static int MinJump(int[] array, int index)
        {
            if(cachedResults.ContainsKey(index))
                return (int)cachedResults[index];

            Console.WriteLine("Evaluating index: " + index);

            if (index >= array.Length - 1)
                return CacheAndReturn(index, 0);

            if (array[index] >= array.Length - index - 1)
                return CacheAndReturn(index, 1);

            int min = Int32.MaxValue;
            for (int x = 1; x <= array[index]; x++)
            {
                int temp = MinJump(array, index + x);
                if (temp < min)
                {
                    min = temp;
                }
            }

            if (min != Int32.MaxValue)
            {
                return CacheAndReturn(index, 1 + min);
            }
            else
            {
                return CacheAndReturn(index, Int32.MaxValue); // no jump
            }
        }

Here is the code in O(n) and O(1) space

#include <stdio.h>
#include <conio.h>

void findJumps(int arr[],int n)
{
	int i,len=0,prev;
	if(arr[0]>n)
	{
		printf(" No of jumps are 1 ");
	}
	else
	{
		for(i=0;i<n;)
		{
			if(i+arr[i]>=n-1)
			{
                          len=len+1;
                          break;
        	}
			i=arr[i+arr[i]];
			if(i==0&&i<=n-1)
			{
				len=len+arr[i];
				break;
			}
			len=len+1;
		}
	}
	if(len==0)
	{
		printf(" No jumps are there ");
	}
	else
	{
		printf(" Number of jumps are %d ",len);
	}
}
int main()
{
	int arr[]={1,5,4,6,9,3,0,0,1,3};
	int n=sizeof(arr)/sizeof(arr[0]);
	findJumps(arr,n);
}

Java Code :

int[] a = {2 ,5 ,9 ,6 ,9 ,3 ,0 ,0 ,1 ,3 ,13};

int min = (a.length - 1 - 0 - a[0]);
int step = a[0];
int max_jump = 1;
int sum = 0;
int index = 0;
String strPosition=0+",";
for (int i = 1; i < a.length; i++) {

--step;
sum = (a.length - 1 - i - a[i]);
if (sum <= min) {
min = sum;
index = i;
}
if (step == 0) {
++max_jump;
step = a[index];
strPosition +=" "+index+",";
}
}


System.out.println(" position "+ strPosition+" number of jumps "+ max_jump);

My implementation of greedy solution suggested by @EOF. Runtime is O(N * L) where N is the size of array and L is the average length of jumps.

#import <stdio.h>

int leastJumps(int *array, int array_length);

int main(){
  int jumps[] = {2,5,0,0,0};
  int least_Jumps = leastJumps(jumps, 5);
  printf("Max jumps: %d\n", least_Jumps);
  return 0;
}

int leastJumps(int *array, int array_length){
  int jumps = 0; // total of number of jumps to reach end

  int curr_index = 0;

  while(1){

    int max_jump_length = array[curr_index]; //  maximum amount you can jump for array[curr_index]

    if(curr_index + max_jump_length >= array_length-1){
      // Can reach end of array with 1 more jump from this position
      jumps++; //jump to end and return
      return jumps;
    }

    int best_index = array[curr_index]; // best index to jump to from array[curr_index]
    for(int j = curr_index+1; (j <= curr_index+max_jump_length && j < array_length); j++){
      if(array[j] > array[best_index]) best_index = j;
    }
    if(array[curr_index] == 0){
      return -1; // Can't jump to end
    }else{
      curr_index = best_index; // jump to best index
      jumps++;
    }
  }

}

The ranges of jumps are more or less mutually inclusive , the only necessary info to maintain is the furthest jump
then you search the furthest jump you can make the next step with in the range you can reach from the last jumps

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

void f(int *ary, int size){
	int bgn, end=-1;// inclusive end, exclusive bgn
	int stp_cnt=0;
	int leap_dst=0;  //the furthest frog can jump next stp
	int ary_end=size-1;
	do{ 
		bgn=end;
		end=leap_dst;
		
		int i;
		stp_cnt+=1;
		for(i=end;i>bgn;i--)
			if(leap_dst<i+ary[i])
				leap_dst=i+ary[i];
		if(leap_dst==end){
			printf("unreachable\n");
			return;
		}
	}while(leap_dst<ary_end);
	printf("%d\n",stp_cnt);
}
main(){
 int ary1[]={1, 5, 4, 6, 9, 3, 0, 0, 1, 3};
 int ary2[]={2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
 f(ary1,10);
 f(ary2,10);
}

Simple python approach using memoization.
Thanks to memoization the inner recursive function is called only once for each array element.

Each call at position i will examine at most n-i elements, so the total number of array accesses is O(n^2), and extra space required is O(n)

def min_steps(a):
  n = len(a)
  if n == 1:
    return 0  #edge case!
    
  steps = [None] * n  #Memoization will help us avoiding redundant recomputation
  
  def rec_min_step(a, i):
    #Invariant: i < n - 1 [edge cases are handled separately, and this function will never recurse on i >= n - 1
    n_steps = float('inf')
    m = a[i]
    
    if i + m >= n - 1:
      #can reach the last element with one jump
      steps[i] = 1
      return 1
    else:
      #test every possible jump, from 1 to the max possible value
      for j in xrange(i + 1, i + m + 1):  #xrange right guard is exclusive
        if steps[j] is None:
          rec_min_step(a, j)  #will assign a value to steps[j]
        if steps[j] < n_steps:
          n_steps = steps[j]
      
      #add to the recursive value 1 for this jump
      steps[i] = n_steps + 1
      return n_steps + 1
  
  return rec_min_step(a, 0)

Python implementation of the greedy algorithm, which requires O(n) time and O(1) space

def greedy_min_steps(a, i=0, steps=0):
  best_jump = i
  best_jump_pos = i
  n = len(a)
  if i == n - 1:
    return 0
    
  m = a[i]
  if m + i >= n - 1:
    return steps + 1
  
  for j in xrange(i + 1, min(n - 1, i + m + 1)):
    s =  a[j] + j
    if s > best_jump_pos:
      best_jump_pos = s
      best_jump = j
      
  if best_jump == i:
    return float('inf')
  else:
    return greedy_min_steps(a, best_jump, steps + 1)

You can test that this and the memoization versione always return the same value

void Main()
{
	int[] input = new []{2, 8, 3, 6, 9, 3, 0, 0, 1, 3};
	Console.WriteLine(FindMinimumJumps(input,0,0));
}

int FindMinimumJumps(int[] input, int currentPosition, int numberOfJumps)
{
	int lastPosition = input.Length - 1;
	if(currentPosition > lastPosition)
		return int.MaxValue;
	else if(currentPosition == lastPosition)
		return numberOfJumps;
	
	int maxJump = input[currentPosition];	
	if(maxJump == 0)
		return int.MaxValue;
	
	int minHops = int.MaxValue;
	for(int i = 1;i<=maxJump;i++)
	{
		minHops = Math.Min(minHops, FindMinimumJumps(input, currentPosition + i,numberOfJumps+1));
	}
	
	return minHops;
}

This can be solved by converting it to graph.
1. Consider each array element A[i] as vertex Vi.
2. Value "val" at A[i] will tell you the connectivity of Vi other vertex Vj.
Vi ----->V(i+1)
|
+-----------------V(i+2)
|
.
+----------------------------------V(i+val)
3. Create adjacency matrix and apply shortest path algo.

In fact given array is the compact form of adjacency list.

Using DP to solve this problem. maybe o(n^2)

public static int getMinJumpCount(int[] data){
		int[] count = new int[data.length];
		
		for(int i = data.length - 2; i >= 0; i--){
			if(data[i] == 0)
				count[i] = 0;
			else if(i + data[i] >= data.length - 1)
				count[i] = 1;
			else{
				count[i] = data.length;
				for(int j = i + 1; j <= i + data[i] && j < data.length; j++){
					if(count[j] != 0 && count[i] >= count[j] + 1)
						count[i] = count[j] + 1;
				}
			}
		}
		return count[0];
	}

None of this makes any sense at all. That question makes absolutely no sense... are you all speaking Klingon?

The simplest code would be:

def jump(a):
    #a = [2, 0, 2, 1, 2];
    steps = 0

    if len(a) == 0 or len(a) == 1:
        return 0

    for i in range(1, len(a)):
        a[i] = max(a[i], a[i-1]-1)

    i=0;

    print a;
    while i<len(a)-1:
        steps+=1
        i+=a[i]
    
    return steps;

We can use BFS to get the solution as below:
[1 5 4 6 9 3 0 0 1 3]
We need to make a Directed acyclic graph for this array and then all we need to do is to find out the minimum number of hops till we reach the destination which is 3 in this case.

Anyway if someone can post a DP solution with clear explanation that would be great.

I prefer to approach this kind of problems backwards - from the end to the beginning.
We can use DP with N states. dp[i] means the minimum amount jumps to go from position i to the end of the array (position N).
A BFS is also perfectly fine here. The time complexity of both algorithms will be the same - O(N * Max_Jump).

// I will assume there is always a valid solution
int minJumps(int jumps[], int n) {
    vector<int> dp(n+1, n*2);// n*2=infinity: n*2 is more than any valid solution
    dp[n] = 0;
    for (int i = n-1; i >= 0; i--)
        for (int j = 1; j <= jumps[i] && i+j <= n; j++) 
            dp[i] = min(dp[i] , 1 + dp[i+j]);
    return dp[0];
}

Here, dp[i] stores minimum steps to reach end from ith position.
Initially, dp[n-1]=0 because frog is at end. Start from right end and go towards left to calculate steps.

#include<stdio.h>
#include<limits.h>
#include<iostream>
#include<stdlib.h>
using namespace std;

int *dp;
void calc(int *a,int index,int n,int steps)
{

	if(index<0)
		return;
   
	int myMin=INT_MAX;
	for(int i=1;i<=a[index] && index+i<n;i++)
	{
		int x = dp[index+i];
		if(x<myMin)
			 myMin = x;
	}
	if(myMin<dp[index]-1)
		dp[index]=myMin+1;
    calc(a,index-1,n,steps+1);
}


int main()
{
	int n;
	cin>>n;
	int *a = (int*)calloc(n,sizeof(int)); 
	dp = (int*)calloc(n,sizeof(int)); 
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		dp[i]=INT_MAX;
	}
	dp[n-1]=0;
	//cout<<calc(a,0,n,0)<<endl;
	calc(a,n-1,n,0);
	cout<<dp[0]<<endl;
	
 	return 0;
}

A Dynamic Programming solution you asked is here>>>

WORST CASE TIME: O(n^2)
EXTRA SPACE: O(n)

1. Create a Jumps[] array.
   Jumps[i] = minimum number of jumps required from index i to reach end.
   Assuming 0-based indexing, Jumps[n-1] = 0 (because "n-1" is the last 
   index of the array).
2. Now,
	if (Array[i] == 0)
		Jumps[i] = INFINITE; //once reached here, cannot jump further...
	else if (Array[i] >= Array.length - i - 1)
		jumps[i] = 1; //can reach the end in a single jump from here...
	else let Array[i] = k (suppose) then
		Jumps[i] = 1 + min(Jumps[i+1], Jumps[i+2], ... , Jumps[i+k])
3. Proceed from right to left and return Jumps[0] as the answer.

NOTE: MAY BE I'VE NOT CONSIDERED SOME BOUNDARY CASES!

I dont know why u asked for DP solution when it can be done by applying simple greedy solution..

public static int findMinumumJump(int array[]){
		if(array == null){
			return -1;
		}

		if(array.length == 1){
			return 0;
		}

		int jumps[] = new int[array.length];

		for(int i = array.length - 2; i >= 0 ; i--){
			if(array[i] == 0){
				jumps[i] = Integer.MAX_VALUE;
				continue;
			}

			if((array[i] + i) >= array.length - 1){
				jumps[i] = 1;
			}
			else{
				int minumnNumber = Integer.MAX_VALUE;
				for(int j = i + 1; (j < array.length - 1) && (j <= array[i] + i); j++){
					if(jumps[j] < minumnNumber){
						minumnNumber = jumps[j];
					}
				}
				jumps[i] = minumnNumber + 1;
			}
		}
		return jumps[0];
	}

Simple

O(n)

solution: the frog looks into the array, and then jumps to the end based on whichever tile he lands on.

def jump(list,qty):
  if len(list) <= qty:
    return 0
  qty += 1
  return 1+jump(list[qty:], list[qty-1])

def main(script,*args):
  list = [1, 5, 4, 6, 9, 0, 0, 1, 3]
  print "arr = ", list, "; frog jumps = ", jump(list, 0)

  list = [2, 8, 3, 6, 9, 3, 0, 0, 1, 3]
  print "arr = ", list, "; frog jumps = ", jump(list, 0)

if __name__ == '__main__':
  import sys
  main(*sys.argv)

I'm not sure I am understanding the question properly but here is an overview of my solution.
Greedy algorithm
Start with the first element and look at all possible locations it can jump to. Ignore them if they are 0.
Example:[1 5 4 6 9 3 0 0 1 3 13]
i 0 1 2 3 4 5 6 7 8 9 10
start at i = 0;
We first look at i = 0 which would give back the set of indecies i = {1}
we look at i = 1 which would give us back the set of indecies i = {2,3,4,5,6}
i = 2 -> {3,4,5,6}, i = 3 -> {4,5,6,7,8,9}, i = 4 -> {5,6,7,8,9,10,11,12,13}, i = 5 -, i > {6,7,8}= 6 -> {}
we choose the index that will give the set with the highest possible index (i = 4)
we look at i = 4 which would produce the set {5,6,7,8,9,10,11,12,13}
we are done since this set contains the last index.

O(n) time

Producing the sets is an easy way of talking about it. For coding purposes, just choosing the (next highest number + the distance) from your current index will get you to your next index.

I still don't understand the question and the example given as how we got the answer as 3 and 2 respectively.