Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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

Author 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.

 

  • If arr[n]=3, and the previous day’s task preTask=1, task A can not be performed; perform task B. But if the previous day’s task preTask=2, perform task A. If no task is performed on the previous day, perform the task that minimizes the number of days with no task performed.

 

Code

#include<bits/stdc++.h>
using namespace std;

//recursive approach
int minDays(int arr[],int preTask,int n)
{
if(n==0)
{
return 0;
}

//if no task available
if(arr[n-1]==0)
{
return 1+minDays(arr,0,n-1); //no task performed
}
// task A is available
else if(arr[n-1]==1)
{
//check the last task performed
//if it is also A, then no task performed
if(preTask==1)
{
return 1+minDays(arr,0,n-1);
}

//otherwise task A performed
else
{
return minDays(arr,1,n-1);
}
}

// task B is available
else if(arr[n-1]==2)
{
//check the last task performed
//if it is also B, then no task performed
if(preTask==2)
{
return 1+minDays(arr,0,n-1);
}

//otherwise task B performed
else
{
return minDays(arr,2,n-1);
}
}

else
{
//check the last task performed
//if it is A, perform task B
if(preTask==1)
{
return  minDays(arr,2,n-1);
}
//check the last task performed
//if it is B, perform task A
else if(preTask==2)
{
return  minDays(arr,1,n-1);
}

//otherwise perform the task 
//that minimizes no of days with no task performed
else
{
return min(minDays(arr,2,n-1),minDays(arr,1,n-1));
}

}
}

//driver code

int main()
{
int n=4;
int arr[] = { 0, 1, 3, 2 };

cout<<"minimum days with no task performed : "<<minDays(arr,0,4);
}

 

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

#include<bits/stdc++.h>
using namespace std;

//2D array to store dp states

int dp[201][3];
//Dynamic programming approach approach
int minDays(int arr[],int preTask,int n)
{
if(n==0)
{
return 0;
}

if(dp[n][preTask]!=-1)
{
return dp[n][preTask];
}
//if no task available
if(arr[n-1]==0)
{
return dp[n][preTask]=1+minDays(arr,0,n-1); //no task performed
}
// task A is available
else if(arr[n-1]==1)
{
//check the last task performed
//if it is also A, then no task performed
if(preTask==1)
{
return dp[n][preTask]=1+minDays(arr,0,n-1);
}

//otherwise task A performed
else
{
return dp[n][preTask]=minDays(arr,1,n-1);
}
}

// task B is available
else if(arr[n-1]==2)
{
//check the last task performed
//if it is also B, then no task performed
if(preTask==2)
{
return dp[n][preTask]=1+minDays(arr,0,n-1);
}

//otherwise task B performed
else
{
return dp[n][preTask]=minDays(arr,2,n-1);
}
}

else
{
//check the last task performed
//if it is A, perform task B
if(preTask==1)
{
return  dp[n][preTask]=minDays(arr,2,n-1);
}
//check the last task performed
//if it is B, perform task A
else if(preTask==2)
{
return  dp[n][preTask]=minDays(arr,1,n-1);
}

//otherwise perform the task 
//that minimizes no of days with no task performed
else
{
return dp[n][preTask]=min(minDays(arr,2,n-1),minDays(arr,1,n-1));
}

}
}

//driver code

int main()
{
int n=4;
int arr[] = { 0, 1, 3, 2 };

memset(dp, -1, sizeof(dp));
cout<<"minimum days with no task performed : "<<minDays(arr,0,4);
}

 

Output

 

minimum days with no task performed : 2

 

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

This article covered how to find the number of days in which no task is performed.

 

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!

 

 

Previous article
Maximize Subsequence Sum after a Plus-Minus Sign Alternatively on Elements
Next article
Maximize Score by Multiplying Elements of Given Array with Given Multipliers
Live masterclass