Last Updated: 29 Sep, 2021

Minimize Time

Moderate

Asked in company

Solve now

Problem statement

Ninja wants to go on a vacation in his summer holidays. But he got a lot of homework from his school which requires a certain amount of time to complete. As the ninja was the topper of the class he was allowed to skip tasks, but cannot skip two consecutive tasks from his homework. You are given an array, ‘ARR’ of ‘N’ integers. Find the minimum time ninja needs to spend to complete the homework.

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains an integer ‘N’, representing the number of tasks.

The second line of each test case contains ‘N’ space-separated integers, representing the time needed to complete each task.

Output Format :

For each test case, print the minimum time needed to complete the homework.

Print the output of each test case in a separate line.

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 <= 5*10^3

Time Limit : 1 sec

Solve now

Approaches

01 Approach

For any ‘ith’ task we have two choices with us whether to include the ‘ith’ task or exclude the ‘ith’ task.

If we include the ‘ith’ task, we again have two choices with us whether to include the previous task or not.
If we exclude the ‘ith’ task we only have one choice by choosing the previous task as we are not allowed to skip two consecutive tasks.

We can maintain an array to keep track of time.

Here is the algorithm :

Base case
- If ‘N’ is smaller than equal to 0, return 0.
Create an array (say, ‘INC’) of size ‘N’ that will store the time of including the tasks and initialize ‘INC[0]’ with ‘ARR[0]’.
Create an array (say, ‘EXC’) of size ‘N’ that will store the time of excluding the tasks and initialize ‘EXC[0]’ with 0.
Run a loop from 1 to ‘N’ (say, iterator ’i’) to traverse each task.
- Update ‘INC[i]’ (include the current task) with the sum of ‘ARR[i]’ and a minimum of ‘EXC[i - 1]’ and ‘INC[i - 1]’
- Update ‘EXC[i]’ (exclude the current task) with the ‘INC[i - 1]’.
Finally, return the minimum of ‘INC[N - 1]’ and ‘EXC[N - 1]’.

Solve now

02 Approach

The idea is similar to the previous approach. We only use the time of ‘i - 1’th task for the ‘ith’ task. So we can save the space by using variables that will store the time of the previous task.

Here is the algorithm :

Base case
- If ‘N’ is smaller than equal to 0, return 0.
Create a variable (say, ‘INC’) that will store the time of including the tasks and initialize it with ‘ARR[0]’.
Create a variable (say, ‘EXC’) that will store the time of excluding the tasks and initialize it with 0.
Run a loop from 1 to ‘N’ (say, iterator ’i’) to traverse each task.
- Create a new variable (say, ‘nInc’) that will store the time including the current task and initialize it with the sum of ‘ARR[i]’ and a minimum of ‘EXC’ and ‘INC’
- Create a new variable (say, ‘nExc’) that will store the time excluding the current task and initialize it with ‘INC’
- Update ‘INC’ and ‘EXC’ with ‘nInc’ and ‘nExc’ respectively.
Finally, return the minimum of ‘INC’ and ‘EXC’.

Solve now