Close
Topic list
Ninja and his Courses
HARD
50 mins
Graph
Dynamic Programming
Bit Manipulation
Topics (Covered in this problem)
Problem solved
Skill meter
Graph
-
-
Dynamic Programming
-
-
Bit Manipulation
-
-
Other topics
Problem solved
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

# Ninja and his Courses

Contributed by
Dhruv Sharma
Hard
0/120
Avg time to solve 50 mins
Success Rate 50 %
Share

## Problem Statement

#### For example:

``````Let‘N’ = 3 , ‘K’ = 1 and ‘DEPENDENCIES’ = [ [1, 2] [2, 3] ].
``````

``````In this example, if you want to take ‘COURSE_3’ then first you have to take ‘COURSE_2’ in the previous semester. If you want to take ‘COURSE_2’, then first you have to take ‘COURSE_1’ in the previous semester.
The value of ‘K’ is 1 which means in a semester we can choose at most 1 course.
``````
Detailed explanation ( Input/output format, Notes, Constraints, Images )
##### Sample Input 1:
``````2
4 3 2
2 1
3 1
1 4
5 0 2
``````
##### Sample Output 1:
``````3
3
``````

#### Explanation for Sample Output 1:

``````For sample test case 1:
``````

``````In the first semester we can choose ‘COURSE_2’ and ‘COURSE_3’ as these are not dependent on other courses. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses. So in the first semester, we choose these two courses.

After that in the second semester:
``````

``````In the second semester, we can choose only the ‘COURSE_1’ as this course is not dependent on other courses. So in the first semester, we choose only one course.

After that in the third semester:
``````

``````In the third semester, only one course is left i.e ‘COURSE_4’.So in the third semester, we choose the last course.

So, the minimum number of semesters required to take all the courses is 3.

For sample test case 2:
``````

``````In this sample test case, no course is dependent on each other i.e all courses are independent. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses.

So in the first semester, we choose ‘COURSE_1’ and ‘COURSE_2’.
In the second semester, we choose ‘COURSE_3’ and ‘COURSE_4’.
In the third semester, we choose the last course i.e. ‘COURSE_5’.

So, the minimum number of semesters required to take all the courses is 3.
``````
##### Sample Input 2:
``````1
5 4 2
2 1
3 1
4 1
1 5
``````
##### Sample Output 2:
``````4
``````

#### Explanation for Sample Output 2:

``````For sample test case 1:
``````

``````In the first semester, we can choose ‘COURSE_2’, ‘COURSE_3’ and  ‘COURSE_4’ as these are not dependent on other courses. The value of ‘K’ is 2 which means in a semester we can choose at most 2 courses. So in the first semester, let us assume we choose ‘COURSE_2’ and ‘COURSE_3’.

After the first semester:
``````

``````In the second semester, we can choose only the ‘COURSE_4’ as this course is not dependent on other courses. So in the second semester, we choose only one course.

After that in the second semester:
``````

``````In the third semester, we can choose only the ‘COURSE_1’ as this course is not dependent on other courses. So in the third semester, we choose only one course.

After that in the third semester:
``````

``````In the fourth semester, only one course is left i.e ‘COURSE_5’.So in the fourth semester, we choose the last course.

So, the minimum number of semesters required to take all the courses is 4.
``````
Auto
Console