I stumbled upon the following problem:
Given an ordered list of cards with integers on them (e.g.
[1,24,3,4,5]), two players take turns to take cards. Player 1 goes first. Whenever either player takes a card with an even number, they reverse the order of the remaining cards, and the game continues. When all cards are taken, they compute their sums. The player with the higher sum wins. If there's a tie, player 1 wins. Write a program, given the sequence of cards, to output the winner.
I use pointers to finish this problem. Create two pointers i = 0 and j = n-1, where n is the total number of cards. Create another pointer k to keep track of where you are. Whenever I encounter an even card, I just switch between i and j.
I wrote a function that works, but it takes O(n), because I do need to traverse the entire list. Is there a quicker way to do this?
By "pointers" you surely mean "indexes". Since the values are not restricted, any of the cards might be a game changer and any of the cards might be pair, therefore you do not have shortcuts. You need to have sumPlayer1, sumPlayer2, both initialized with 0, starting to read cards and each time you read a card, you add its value to the appropriate player.
You start to read the cards from the "left" and when you encounter the first pair number, you switch to reading from the right, until you find the first pair and so on, switching back-and-forth, according to the rules of the game until you run out of cards.
And since this will read all the cards, you will have a linear algorithm as you already have and you cannot go lower than that in complexity. If you have some restrictions or constraints, then we may optimize the algorithm, but without further information, linear is the best you can get.