Determine if first player can win a game or not

Question

Consider the following game. There's an array of positive numbers. Each player in turn removes a slice (consecutive sequence of elements) such that it's sum is even. The player to lose is the player that cannot make a move. For the [4, 5, 3, 7, 2] example, the winning strategy (for first player) is removing the[5,3]slice. You need to determine if the first player has a winning move (if yes, return the slice_start and slice_end indexes).

Time/Space complexity: O(n)

One natural thing I came up with is to calculate the accumulative sum from left to right and vice versa. In the [4,5,3,7,2] example we get: acc_l = [4,9,12,19,21] and acc_r = [21,17,12,9,2].

So I'm almost certain those two auxiliary arrays should come in handy but I couldn't figure it out completely.

I'd be glad for help!

Answer 1

Calculate sum of whole array. Check if it's even or odd. Also count number of even and odd numbers in the array (all in one pass). That should help you figure out your answer.