See the original problem on HackerRank.
Solutions
Checking if a certain value \(x\) is suitable takes linear time.
Intuitively, we have to verify if the array can be splitted into contiguous groups of sum \(x\), without remainder (empty space on the bus is not allowed).
This operation consists in iteratively checking the prefix sum of the array against a cumulative value of \(x\).
For example:


Suppose we want to the check if 3
works. The prefix sum of the array is here below:


Starting from 3
we find that such a value is present. Then we sum 3
to itself, getting 6
and check if this value is present. It is. We move on to 9
and finally to 12
.
On the other hand, let’s try  for example  with 8
:
We find 8
in the prefix sum array but we fail to find 16
.
The other values working are, indeed, 4
, 6
and 12
.
Note that calculating the prefix sum is not mandatory, however the algorithm is just easier to understand and simpler to write.
It’s easy to see that only divisors of the array sum work, since we are not allowed to leave empty space on the bus.
So here is the idea:
 calculate the prefix sum (using the array itself as storage is just fine)
 the last value of the prefix sum is  by definition  the sum of the original array
 for each element of the prefix sum array, run the check discussed above only on divisors of the sum
 along the way, print the divisors for which the check worked
This costs \(O(N \cdot M)\), where \(M\) is the maximum number of divisors for the domain (\(10^4 \cdot N\)).
Here is an implementation:


Note that the internal while loop (together with the nested call to find
) is linear: each element is visited at most once! For instance:


Suppose we want to check 3
 as before.
val = 3
and it
points to the beginning of the array.
In the while
loop, find
ends up pointing to the second element.
Then val
is updated to 6
.
Now find
starts from the second position (begin + 1
) and gets back an iterator to the position 4
(begin + 4
). Still, all the elements along the way were only visited once.
9
and 12
follow a similar workflow.
Using a binary search was also a correct and acceptable solution. Here is just the while loop:


We can even refactor the code a bit and end up with the following snippet:


Playing with patterns
The previous solution sets a new challenge: is it possible to write check
in terms of any patterns?
Think about it, for a moment.
Sometimes patterns bring out by seeing the code from another perspective.
Actually, check
just verifies that a vector v
contains all the values of divisor
summed up to itself a certain number of times (that is \(\dfrac{sum}{divisor}\)).
For example, given that v
is:


If we call check(v, 3)
we are basically checking that v
contains:


Since val
is updated by repeateadly adding 3
to it up to 12
(the value of sum
).
Does it make sense?
Thus, we should search for a pattern that checks if a range includes another one. The pattern may require both sequences to be sorted but this is not a problem for us since v
is sorted by definition (the prefix sum of positive integers is always monotonic ascending).
We are lucky enough to discover that such a pattern exists! std::includes
checks if one set is a subset of another.
The sequence to check against is just the prefix sum of \(k\) copies of the divisor value (\(k = \dfrac{sum}{divisor}\)).
So we can rewrite check
this way:


Although the overall complexity does not change, this version is more expensive than the other because we allocate extra space and we do an extra iteration.
If you are a dynamic C++ developer, you know that C++20 ships ranges and you should play with them.
With ranges, we can rewrite check
without allocating extra space nor performing an extra iteration. The solution is one line of code:


Briefly:
 we use
repeat_n
to generate a lazy sequence ofv.back()/divisor
values equal todivisor
 on that we run
partial_sum
to obtain the lazy sequence of cumulative sums of such values includes
works like before
Here is a link to a working example.
It’s interesting to see that we do not allocate extra space nor run unnecessary iterations on the sequence.
Even more interesting, we have found patterns to solve the problem. Food for our brain.