Last Updated: 11 Feb, 2022
Candies For Students
Easy
Asked in companies
You are given an array of ‘MARKS’ of students, where ‘marks[i]’ represent the marks of ‘i’th student. You want each student to have a minimum of 1 candy. If two students are sitting next to each other, the one with higher marks should get more candies. Find the minimum number of candies required to distribute to all students.
For Example:
You are given ‘MARKS’ = [7, 10, 9, 5], Here you can distribute candies as [1, 3, 2, 1]. Here all the students with higher marks than the students sitting beside them also have more candies. Hence the answer is 7.
Input Format:
The first input line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains a single integer ‘N’ representing the number of students.
The second line of each test case contains ‘N’ space-separated integers, representing the marks of each student.
Output Format:
Print a single integer for each test, representing the minimum number of candies required to distribute to all students.
Print a separate line for each test case.
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10000
0 ≤ MARKS[i] ≤ 10^5
Time Limit: 1 sec.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
In this approach, we will try to start with distributing one candy to each child and then check if any child who has more rating than one of the neighbours should have more candy than its neighbour. So, distribute one more candy to that child who does not satisfy the above condition. Do this until every child is satisfied.
Algorithm:
- Create an array ‘candies’, with all values initialized to ‘1’
- Set ‘updated' to True
- While ‘updated’ is True
- Set ‘updated’ to False
- Iterate over the ‘marks’ and check if ‘ith’ students marks are greater than ‘i - 1’th student, if it updates ‘candies[i]’ to ‘candies[i - 1] + 1’ and set ‘updated’ to True
- If ‘ith’ students marks are greater than ‘i + 1’th student, if it is update ‘candies[i]’ to ‘candies[i + 1] + 1’ and set ‘updated’ to True
- Return the sum of all values in ‘candies’.
In this approach, we will first try to only match the given condition from the left side and then from the right side. First, we give 1 candy to everyone and traverse the array from left to right. If a student has more marks than the student on his left side we increase the current student’s candy to be one more than the left student. Then we do the same thing for the student in right while traversing the array from right to left.
Algorithm:
- Create an array ‘candies’ equal to the size of ‘marks’, initialise with all ‘1’s
- Iterate ‘i’ through 0 to ‘length of marks - 1’
- If marks[i] is greater than marks[i + 1]
- Set ‘candies[i]’ as ‘candies[i + 1]’ + 1
- If marks[i] is greater than marks[i + 1]
- Iterate ‘i’ from ‘length of marks - 2’ to ‘0’
- If ‘marks[i] is greater than ‘marks[i + 1]’ and candies[i] is not greater than ‘candies[i+ 1]’.
- Set ‘candies[i]’ as ‘candies[i + 1]’ + 1
- If ‘marks[i] is greater than ‘marks[i + 1]’ and candies[i] is not greater than ‘candies[i+ 1]’.
- Return the sum of all elements of ‘candies’ array