Frog Jump

Easy
0/40
Average time to solve is 30m
profile
Contributed by
751 upvotes
Asked in companies
MicrosoftDunzoCIS - Cyber Infrastructure

Problem statement

There is a frog on the '1st' step of an 'N' stairs long staircase. The frog wants to reach the 'Nth' stair. 'HEIGHT[i]' is the height of the '(i+1)th' stair.If Frog jumps from 'ith' to 'jth' stair, the energy lost in the jump is given by absolute value of ( HEIGHT[i-1] - HEIGHT[j-1] ). If the Frog is on 'ith' staircase, he can jump either to '(i+1)th' stair or to '(i+2)th' stair. Your task is to find the minimum total energy used by the frog to reach from '1st' stair to 'Nth' stair.

For Example 
If the given ‘HEIGHT’ array is [10,20,30,10], the answer 20 as the frog can jump from 1st stair to 2nd stair (|20-10| = 10 energy lost) and then a jump from 2nd stair to last stair (|10-20| = 10 energy lost). So, the total energy lost is 20.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer,' N’, denoting the number of stairs in the staircase,

The next line contains ‘HEIGHT’ array.
Output Format: 
For each test case, return an integer corresponding to the minimum energy lost to reach the last stair.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 100000.
1 <= HEIGHTS[i] <= 1000 .

Time limit: 1 sec
Sample Input 1:
2
4
10 20 30 10
3
10 50 10
Sample Output 1:
20
0
Explanation of sample input 1:
For the first test case,
The frog can jump from 1st stair to 2nd stair (|20-10| = 10 energy lost).
Then a jump from the 2nd stair to the last stair (|10-20| = 10 energy lost).
So, the total energy lost is 20 which is the minimum. 
Hence, the answer is 20.

For the second test case:
The frog can jump from 1st stair to 3rd stair (|10-10| = 0 energy lost).
So, the total energy lost is 0 which is the minimum. 
Hence, the answer is 0.
Sample Input 2:
2
8
7 4 4 2 6 6 3 4 
6
4 8 3 10 4 4
Sample Output 2:
7
2


Hints:
1. Think about all the possibilities at each stair.
2. Using recursion, try to divide the problem into subproblems and calculate the answer for each subproblem only once - store it for reusing in the future.
3. The above can also be done iteratively.
Approaches (3)
Recursion

In this approach, we will define a recursive function REC(i,HEIGHT) that will return the minimum energy needed to reach the last stair from the ith stair.

The base case will be if i is greater than or equal to ‘N’ answer will be 0 as we already reached the final stair.

As we have two choices at each step,REC(i) will be the maximum of energy lost for jumping from ith to (i+1)th step + REC(i+1) and energy lost for jumping from i th to (i+2)th step + REC(i+2).

 

The final answer will be REC(1, HEIGHTS) corresponding to the minimum energy required to reach the last stair from the first stair.

 

Algorithm:

  • Defining 'REC'(i,’ HEIGHTS’) function :
    • If i is equal to the length of ‘HEIGHTS’ - 1:
      • Return 0.
    • Set ‘ONE_JUMP’ as INF.
    • Set ‘TWO_JUMP’ as INF.
    • If i+1 < length of ‘HEIGHTS’:
      • Set ‘ONE_JUMP’ as abs(HEIGHTS[i]-HEIGHTS[i+1]) + REC(i+1,HEIGHTS).
    • If i+2 < length of ‘HEIGHTS’:
      • Set ‘TWO_JUMP’ as abs(HEIGHTS[i]-HEIGHTS[i+2]) + REC(i+2,HEIGHTS).
    • Set ‘ANS’ as minimum of ONE_JUMP and TWO_JUMP.
    • Return ‘ANS’.
  • Set ‘ANS’ as REC(1,HEIGHTS).
  • Return ‘ANS’.
Time Complexity

O(2^N), where ‘N’ is the number of stairs.

 

In this approach, in the worst case, we will run the 'REC' function for all possible combinations. Each stair has two choices. So the total number of combinations is 2^N. Hence the overall time complexity is O(2^N).

Space Complexity

O( 2^N), where ‘N’ is the number of stairs.

 

In this approach, in the worst case, we are making 2^N calls of the 'REC'() function. It will consume stack memory. Hence the overall space complexity is O(2^N).      

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Frog Jump
Full screen
Console