1.
Introduction
2.
Problem statement
3.
Approaches
4.
Complexity analysis
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

# Minimum Number of Days in which No Task is Performed

Malay Gain
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction

Here we will be discussing an interesting problem. We will cover two approaches to solve this problem. First, we will see the native recursive approach and then implement the dynamic programming-based solution using the concept of memoization.

## Problem statement

You are given an array consisting of 0,1,2,3 only where the value at ith index represents some specific work that can be done on the ith day.

0 represents no tasks available on that day.

1 represents task type A available for that day.

2 represents task type B available for that day.

3 represents both tasks A and B available for that day. You can perform any one of your choices.

Provided that you canâ€™t perform the same type of task on two consecutive days, you need to find the minimum number of days in which no task is performed.

Input

arr[ ] = { 0, 1, 3, 2 }

Output

minimum days with no task performed = 2

Explanation

On the 0th day, no task is performed as arr[0]=0,i.e count=1. On 1st day, task A can be performed. On the 2nd-day task B can be performed, as pervious dayâ€™s task is A. But on the 3rd-day task B can not be performed as the previous dayâ€™s task was B. So, no task is performed on the 3rd day. Therefore, count=1+1=2

Note: Please try to solve the problem first and then see the below solution approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approaches

Recursive approach

We will use a recursive function to count the minimum number of days in which no task is performed.

• We will pass an argument to keep track of the current index of the arr[ ] and preTask to keep track of the previous dayâ€™s task.

• If arr[n]=0, no task is available for that day. So, increase the count of days with no task performed.
• If arr[n]=1, task A can be performed. But if the previous dayâ€™s task preTask=1, task A can not be performed (as the same type of task on two consecutive days is not allowed). In that case, increase the count and make the recursive call for the next index.

• If arr[n]=2, task B can be performed. But if the previous dayâ€™s task preTask=2, task B can not be performed. In that case, increase the count and make the recursive call for the next index.

Code

Memoized approach(DP based)

To optimize the recursive approach, we can use the memoization technique to store the previously calculated states and use them to calculate the unknown states. This approach of dynamic programming reduces the repeated calculation of the same state.

Code

Output

## Complexity analysis

The time complexity of the above approach is O(n) where n is the size of the array and space complexity is also O(n).

## FAQs

1. What is Dynamic programming?
Dynamic Programming is a technique of optimizing over recursion by storing the answer for the overlapping subproblems and using that result for the same problem in the future. So, it saves the time of re-computing the answer for the same problem and helps to reduce the exponential time complexity to polynomial time complexity.

2. Mention some applications of Dynamic programming?
This programming technique is used for mathematical optimization problems, time-sharing, robotics control, flight control as well as a reliability design problem.

## Key Takeaways

We highly recommend going through the articles on dynamic programming to grasp the concepts clearly.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Check out this problem - Count Ways To Reach The Nth Stair

Happy learning!

Live masterclass