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 exame 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 than v[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.