See the original problem on HackerRank.
Solutions
Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to \( t \).
Here is a C++ implementation:


The solution is \( O(N \cdot logN) \).
Similarly, a valid solution consists in summing up the first exam values incrementally until the sum is less than or equal to t
:


This snippet leads to recognizing a few patterns:
 prefix sum
 take while a certain condition holds
We have the opportunity to express such patterns with C++ ranges:


Note: the execution of partial_sum
is totally lazy (e.g. it does not run when the condition gets false).
We can even run the partial_sum
on the whole array and do a binary search to quickly find the target:


Having fun with sorting
Our practice at Coding Gym includes experimenting and getting the most out of each challenge.
In the solutions above we have sorted the whole array before running the core algorithm.
Consider the observation:
we should sort only the first
t
elements of the exams array
In other words, knowing that each exam is at least 1, if t
is less than n
, we can avoid sorting the whole array but instead we can work only on the first t
elements.
In the following snippets, we'll ignore the patterns we can successfully apply on the core algorithm (discussed in the section above).
One possible solution consists in using partial_sort
that might be better when t
is way less than n
:


Another solution consists in getting the t
th position sorted and then sorting all the previous elements.
This can be done with the Quick Select algorithm that in C++ is implemented as nth_element
:


Only when \( t < n \), we apply nth_element
which:
 sets at the
t
th position the element what would be there if the array was sorted  puts before the
t
th position all elements less thanv[t]
 for the previous condition, we can just sort the first
t
elements (std::sort
is fine here)
The scope here is to let our brain think, experiment with different tradeoffs and learn new patterns and concepts. For example, learning about Quick Select might be very interesting. This simple challenge led us to enter more advanced concepts on tiptoes.
What about heap?
Andrea Battistello found another awesome solution making use of heaps:


This solution works also online. Suppose we have the following input:


We read 4
and we push it into the heap. We can now read 6
hours of chapters (104
).
Then we read 1
and we push it into the heap. We can now read 5
hours.
Then we read 5
and we push it into the heap. Now we have no more hours left.
Then we read 6
and we ignore it since it's bigger than the top of the heap (aka: studying this chapter would not give any advantage).
When we read 2
and since it is smaller than the top of the heap (5
), we push it into the heap and remove the top (5
).
Now the heap contains:


And 3
hours left!
Then we read 1
and we push it into the heap. Now we have 2
hours left. Then we read 2
and we push it into the heap. Now we do not have any hours left.
The heap contains the following values:


Finally, we read 1
and we push it into the heap, popping 4
at the same time.