Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is the Set in this approach?
3.2.
What is the brute force approach for this problem?
3.3.
Can we use sorting for this problem?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Minimum Number Of Days To Debug All Programs

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This blog will discuss the approach to calculate the minimum number of days to debug all programs. Before jumping on the approach of the problem to calculate the minimum number of days to debug all programs, let’s first understand the problem,

In this problem, we need to return the minimum number of days required to debug all programs. We’ll be given the array which consists of the time to debug a particular program and an integer value which states the time of the working session. Working Session states the atmost time which one can consecutively devote and then take a break. In this, if that time is less than 6 hours then we can complete two working sessions in one day otherwise only one working session per day and it is also given that maximum number of jobs at any time is less than or equal to 14.

For Example:

Input:- 
codeTime[] = {1,2,3,1,1,3}
Working session time:- 4 

Output:- 
2

Explanation:- 
We can complete the first and third task in the first working session, the fourth and sixth tasks in the second working session, and the second and fifth tasks in a third working session.
Therefore, 2 working days as working sessions time is less than 6, so we can opt for two working sessions in one day, therefore a minimum of 2 days are required to debug all programs. 

Approach

The approach of this question is to consider all the possible subsets, and then find the minimum number of days among them. To implement this we will try to do this for each job, either try to put them in the current session, and make a new session for each job, and then take the minimum of both of the cases. There are many overlapping subproblems, so to optimize this we will dp array to store the values of the already processed elements. 

Steps of Algorithm

Step 1. Make a boolean array of size n, to store which elements are processed, and which are not. We will denote processed elements as true, and not processed elements as false. 

Step 2. Make a dp array of size [1<<14][15], because at max, we can have 14 jobs, and initialize all with -1. 

Step 3. We will try to process each job in the current session, make a new session for each job, and return a minimum of both the answer. 

Step 4. We can include the task in the current session if the remaining time is greater than the time of that particular task, and then we need to update the remaining time. If not greater than the time of that task, then create a new session and increment the number of sessions.

Step 5. We will convert the boolean array into an integer by calling boolTonumber, as this denotes the current state of the processed elements, and will check in the dp array if it was already processed or not. 

Step 6. Base case will be, when all the elements are processed, we will check this using the isProcessed array, if it contains all try, we simply return 1. 

Step 7: After calculating all the sessions, we will find number of days, by comparing the sessionTime, if it greater than 6, then number of session = number of days, otherwise,if session time is less than 6, then if number of sessions are odd, number of days = (number of sessions/2) + 1, else number of days = (number of sessions/2).

Implementation in C++

#include<bits/stdc++.h>

using namespace std;
// function to check if all elements are processed or not
// if everything is true, then return true
// as all elements are processed otherwise return false
bool check(vector < bool > & isProcessed, int n) {
  for (int i = 0; i < n; i++) {
    if (isProcessed[i] == false) return false;
  }
  return true;
}
// convertung the boolean array into number
// so to check and save the current state into the dp array
int boolToNumber(vector < bool > & isProcessed, int n) {
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (isProcessed[i] == true) {
      ans += pow(2, i);
    }
  }
  return ans;
}
// function to find out the minimum sessions to complete all the job
int solve(int codeTime[], int n, int currTime, int sessionTime, vector < bool > & isProcessed, vector < vector < int >> & dp) {
  if (currTime > sessionTime) return 1e9;

  // if all are processed
  if (check(isProcessed, n)) return 1;

  int mask = boolToNumber(isProcessed, n);

  // checking the current state is already processed or not
  if (dp[mask][currTime] != -1) return dp[mask][currTime];

  int ans = 1e9;
  for (int i = 0; i < n; i++) {
    if (isProcessed[i] == false) {
      // mark as processed
      isProcessed[i] = true;
      // try to include in the current session
      int include = solve(codeTime, n, currTime + codeTime[i], sessionTime, isProcessed, dp);
      // make new session
      int notInclude = 1 + solve(codeTime, n, codeTime[i], sessionTime, isProcessed, dp);
      // again mark as unprocessed to explore the other paths
      isProcessed[i] = false;
      // cout << ans << " ";
      ans = min(ans, min(include, notInclude));
    }
  }
  return dp[mask][currTime] = ans;

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

  vector < bool > isProcessed(n, false);
  vector < vector < int >> dp(1 << 15, vector < int > (15, -1));
  int numberOfsessions = solve(codeTime, n, 0, sessionTime, isProcessed, dp);
  int ans;
  // if session time is less than 6.
  // calulate the number of days

  if (sessionTime < 6) {
    if (numberOfsessions % 2 == 0) {
      ans = numberOfsessions / 2
    } else {
      ans = numberOfsessions / 2 + 1;
    }
  } else {
    ans = numberOfsessions;
  }
  cout << "Minimum number of days required : " << ans << endl;
}

 

Output

Minimum number of days required: 2

Complexity Analysis

Time Complexity: O(2 ^ N * SessionTime * N)

Incall to ‘getResult()’, we are calculating for each task in the array which is of size ‘N’, and then we are calculating the minimum sessions, therefore the overall time complexity is O(2 ^ N * SessionTime * N), where ‘N’ is the size of the ‘time_input’ vector.

Space Complexity: O(2 ^ N * SessionTime)

As we are using a DP table of at max ‘2 ^ N * SessionTime’ size, therefore, the overall space complexity will be O(2 ^ N * SessionTime).

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

Frequently Asked Questions

What is the Set in this approach?

The Set used in this approach is a type of storage that uses the tree as its storage, and it stores elements in sorted order, in other words, it is a self-balancing BST.

What is the brute force approach for this problem?

The brute force approach for this problem is to use two nested loops, in which we check the whole array for a particular element and compute the closest element for that respective element.

Can we use sorting for this problem?

Yes, we can use sorting for this problem, in which we have to sort all the elements of the ‘input’ array, and we need to traverse from right to left and find the closest element.

Conclusion

In this article, we discussed finding the minimum number of days to debug all programs and the approach to solve this problem programmatically, the time and space complexities.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
DP with Bitmasking
Next article
Number of Ways to Wear Different Hats to Each Other
Live masterclass