Bus Trip

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:

1

1 2 1 1 1 2 1 3

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

1

1 3 4 5 6 8 9 12

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int main()
{
    int N; cin >> N;
    vector<int> v(N);
    partial_sum(istream_iterator<int>(cin), istream_iterator<int>(), begin(v));
    auto sum = v.back();
    
    for (auto i : v)
    {
        if (sum % i == 0) // divisor?
        {
            auto val = i; // accumulator
            auto found = true;
            auto it = begin(v);
            while (val < sum)
            {
                it = find(it, end(v), val);
                if (it == end(v))
                {
                    found = false;
                    break;
                }
                val += i;
            }
            if (found)
                cout << i << " ";
        }
    }
}

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

1

1 3 4 5 6 8 9 12

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

while (val < sum)
{
    lb = lower_bound(lb, end(v), val);
    if (lb == end(v) || *lb != val)
    {
        found = false;
        break;
    }
    val += div;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

bool check(const vector<int>& v, int divisor)
{
    const auto sum = v.back();
    auto val = divisor;
    auto it = begin(v);
    while (val < sum)
    {
        it = find(it, end(v), val);
        if (it == end(v))
        {
            return false;
        }
        val += divisor;
    }
    return true;
}

int main()
{
    int N; cin >> N;
    vector<int> v(N);
    partial_sum(istream_iterator<int>(cin), istream_iterator<int>(), begin(v));
    auto sum = v.back();
    
    copy_if(begin(v), end(v), ostream_iterator<int>(cout, " "), [&](auto i){
       return sum % i == 0 && check(v, i);
    });
}

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:

1

1 3 4 5 6 8 9 12

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

1

3 6 9 12

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:

1
2
3
4
5
6
7

bool check(const vector<int>& v, int divisor)
{
    //           size ----v             v---- fill value
    vector<int> parts(v.back() / divisor, divisor);
    partial_sum(begin(parts), end(parts), begin(parts));
    return includes(begin(v), end(v), begin(parts), end(parts));
}

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:

1

return ranges::includes(v, ranges::views::partial_sum(ranges::views::repeat_n(divisor, v.back()/divisor)));

Briefly:

• we use repeat_n to generate a lazy sequence of v.back()/divisor values equal to divisor
• 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.