See the original problem on HackerRank.
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
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
telements 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
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
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
Only when \( t < n \), we apply
- 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
- 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.