Candies For Students

Easy
0/40
profile
Contributed by
0 upvote
Asked in companies
WalmartRaceIT Delivery

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4
7 10 9 5
3
10 10 10
Sample Output 1:
7
3
Explanation For Sample Input 1:
For the first test case, ‘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.

For the second test case, ‘MARKS’ = [10, 10, 10], Here all the students have equal marks hence they can be given an equal number of candies, so we will distribute the candies as [1, 1, 1]. Hence the answer is 3.
Sample Input 2:
2
4
4 3 1 10
1
10000
Sample Output 2:
8
1
Hint

Try the brute force approach

Approaches (2)
Brute Force

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’.
Time Complexity

O( N ^ 2 ), where N is the number of students.

 

We are iterating over the entire array until no updates are required which will take ~N^2 time.

Hence the final time complexity is O( N ^ 2 ).

Space Complexity

O( N ), where N is the number of students.

 

We are maintaining an array of for candies each student which will take ~N space.

Hence the overall space complexity is O( N )

Code Solution
(100% EXP penalty)
Candies For Students
Full screen
Console