Gaming Array

See the original problem on HackerRank.

Solutions

The naive solution consists in simulating the game: until no elements are left, continuously remove the maximum element and the elements on its right. This might be simplified a bit by performing only a “logical” removal, keeping an index updated to the rightmost element still in the valid range. For example:

1
2
3

5 4 6 9 7
        ^
        last element in range

Bob “removes” 9:

1
2
3

5 4 6 9 7
    ^
    last element in range

It’s clear now that 7 is not in range anymore so Andy picks 6. Finally, Bob wins by picking 5.

This solution is quadratic and shown just for completeness:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

string gamingArray(vector<int> arr) 
{    
    auto tail = end(arr);
    bool bobPlaying = true;
    while (distance(begin(arr), tail))
    {
        tail = max_element(begin(arr), tail);
        bobPlaying = !bobPlaying;
    }
    return bobPlaying ? "ANDY" : "BOB";
}

An improvement consists in speeding up the searching for the maximum element. An idea is to use a support array with the element indexes sorted after the element values. For example:

1

5 4 6 9 7

Then we create this support array:

1

3 4 2 0 1

That contains the indexes of the elements sorted in descending order (9 7 6 5 4).

We play as before, however we now iterate the maximum elements only once instead of visiting the array all the time.

Bob picks arr[3] (that is 9) and updates the last valid index to 3. The index of the next maximum element is not simply the next one but is also one that is strictly less than 3. For this reason, arr[4] (that is 7) is skipped (indeed, 7 is just after 9 in the original array) and arr[2] is chosen instead.

The code speaks for itself:

 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

string gamingArray(vector<int> arr) 
{
    vector<size_t> maxs(arr.size()); // support array
    iota(begin(maxs), end(maxs), 0); // increasing indexes
    sort(begin(maxs), end(maxs), [&](auto i, auto j){ // sort indexes by array values
       return arr[i] > arr[j];
    });
    size_t tail = arr.size(); // maximum valid index
    auto currMax = begin(maxs);
    bool bobPlaying = true;
    while (currMax != end(maxs))
    {
        // find next maximum value whose index is less than tail
        if ((currMax = find_if(currMax, end(maxs), [=](auto m){
            return m < tail;
        })) != end(maxs))
        {            
            tail = *currMax; // logically remove all elements on the right
            ++currMax;
            bobPlaying = !bobPlaying;
        }             
    }

    return bobPlaying ? "ANDY" : "BOB";
}

This solution is as expensive as the sorting algorithm (\( O(N \cdot logN) \) in this case) but it works on all test cases.

A better solution is actually more fun and way easier.

Linear solution

To find a better solution we should play the game…the other way around!

Consider again the following sample case:

1

5 4 6 9 7

Imagine we are playing the last move of the game.

We are in this state:

1

5 4

Evidently, we pick 5 and win the game since 4 is dropped as well.

The input array at the last state of the game just contains the very first element and all the next elements that are smaller than it. It can’t be otherwise because any number bigger than 5 have been already picked in previous moves.

Going on with this rewind, we find the state at the second to last move:

1

5 4 6

Again, 9 and 7 can’t be here at this point because they have been already picked and removed before.

Going back we are at the first state:

1

5 4 6 9 7

Here, 7 is included because smaller than 9.

The total number of moves is 3:

  • 1: Bob removes 9 (and drops 7 as well)
  • 2: Andy removes 6
  • 3: Bob removes 5 (and drops 4 as well) and wins

Bob wins. The good news is that we can deduce the winner by checking if the number of moves is even or odd (Bob wins if odd, Andy does otherwise). So, the problem turns into the computation of the number of moves.

The “rewind logic” explained above should be familiar. It consists in iterating the array to keep track of the maximum element. The number of times the maximum is updated corresponds to the number of moves!

Talk is cheap, show me the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

string gamingArray(vector<int> arr) 
{
    auto runningMax = 0;
    auto moves = 0;
    for (auto i : arr)
    {
        if (i > runningMax)
        {
            runningMax = i;
            moves++;
        }
    }
    return moves % 2 ? "BOB" : "ANDY";
}

This solution is smooth and efficient (linear). For completeness, consider that we don’t even need to copy the input values into an array. The proposed solution is online:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int main()
{
    int g, n, i;
    cin >> g;
    while (g--)
    {
        cin >> n;
        auto runningMax = 0;
        auto moves = 0;
        while (n--)
        {
            cin >> i;
            if (i > runningMax)
            {
                runningMax = i;
                moves++;
            }
        }
        cout << (moves % 2 ? "BOB" : "ANDY") << "\n";
    }
}

Note that numbers can’t be lower than 1, this means runningMax = 0 is fine. In general, to handle negative numbers, it should start from INT_MIN.

To have more fun, which patterns do you see here?

When we calculate a “running thing”, it should smell like a prefix sum. Indeed, here is the trace of an imaginary array containing the maximum elements of 5 4 6 9 7:

1

5 5 6 9 9

At this point, the number of moves corresponds to the number of unique elements in this array:

1

5 6 9

Here are a couple of ways to turn this idea into C++ code:

1
2
3
4
5
6

string gamingArray(vector<int> arr) 
{
    set<int> maxs;
    partial_sum(begin(arr), end(arr), inserter(maxs, begin(maxs)), [](auto a, auto b) { return max(a, b); });
    return maxs.size() % 2 ? "BOB" : "ANDY";
}

Or using the input array as storage:

1
2
3
4
5

string gamingArray(vector<int> arr) 
{
    partial_sum(begin(arr), end(arr), begin(arr), [](auto a, auto b) { return max(a, b); });
    return distance(begin(arr), unique(begin(arr), end(arr))) % 2 ? "BOB" : "ANDY";
}

We can even apply C++20 ranges (actually, Niebler’s range-v3) and get to this beautiful piece of code:

1
2
3
4

std::string gamingArray(const std::vector<int>& arr) 
{    
    return distance(views::partial_sum(arr, [](auto a, auto b) { return max(a, b); }) | views::unique) % 2 ? "BOB" : "ANDY";
}

The very same idea in Python, using a set for simplicity:

1
2

def gamingArray(arr):
    return "BOB" if len(set(list(itertools.accumulate(arr, max)))) % 2 else "ANDY"

In Python, a possible approach to remove adjacent duplicates - as unique in C++ - consists in applying groupby:

1
2

def game_winner(arr):
    return "BOB" if len([key for key, _ in itertools.groupby(itertools.accumulate(arr, max))]) % 2 else "ANDY"

Since groupby groups consecutive identical values, and we take only the “key” for each group.

Here you are an Haskell implementation of the same idea:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

-- | Count the number of moves needed to end the game.
--   Note: This solution also handles negative input values.
countMoves :: (Ord a) => [a] -> Int
countMoves = length . group . scanl1 max

gamingArray :: (Ord a) => [a] -> String
gamingArray =
  let
      -- | Get the name of the winner (note: Bob always starts).
      getWinner m = if odd m then "BOB" else "ANDY"
   in getWinner . countMoves
prefix-sum  patterns  games 
We've worked on this challenge in these gyms: modena  milan 
comments powered by Disqus