Hackerrank - Gaming Array Solution
3 min read

Hackerrank - Gaming Array Solution

Hackerrank - Gaming Array Solution

Andy wants to play a game with his little brother, Bob. The game starts with an array of distinct integers and the rules are as follows:

  • Bob always plays first and the two players move in alternating turns.
  • In a single move, a player chooses the maximum element currently present in the array and removes it as well as all the other elements to its right. For example, if the starting array , then it becomes  after the first move because we remove the maximum element (i.e., ) and all elements to its right (i.e.,  and ).
  • The modifications made to the array during each turn are permanent, so the next player continues the game with the remaining array. The first player who is unable to make a move loses the game.

Andy and Bob play  games. Given the initial array for each game, find and print the name of the winner on a new line. If Andy wins, print ANDY; if Bob wins, print BOB.

To continue the example above, in the next move Andy will remove . Bob will then remove  and win because there are no more integers to remove.

Function Description

Complete the gamingArray function in the editor below. It should return a string that represents the winner, either ANDY or BOB.

gamingArray has the following parameter(s):

  • arr: an array of integers

Input Format

The first line contains a single integer , the number of games.

Each of the next  pairs of lines is as follows:

  • The first line contains a single integer, , the number of elements in .
  • The second line contains  distinct space-separated integers  where .

Constraints

  • Array  contains  distinct integers.

For  of the maximum score:

  • The sum of  over all games does not exceed .

For  of the maximum score:

  • The sum of  over all games does not exceed .

Output Format

For each game, print the name of the winner on a new line (i.e., either BOB or ANDY).

Sample Input 0

2
5
5 2 6 3 4
2
3 1

Sample Output 0

ANDY
BOB

Explanation 0

Andy and Bob play the following two games:

Initially, the array looks like this:

image

In the first move, Bob removes  and all the elements to its right, resulting in :

image

In the second move, Andy removes  and all the elements to its right, resulting in :

image

At this point, the array is empty and Bob cannot make any more moves. This means Andy wins, so we print ANDY on a new line.

  1. In the first move, Bob removes  and all the elements to its right, resulting in . As there are no elements left in the array for Andy to make a move, Bob wins and we print BOB on a new line.

Sample Input 1

2
5
1 3 5 7 9
5
7 4 6 5 9

Sample Output 1

BOB
ANDY

Explanation 1

In the first test, they alternate choosing the rightmost element until the end. Bob, Andy, Bob, Andy, Bob.

In the second case, Bob takes , Andy takes .

Solution in Python

def gamingArray(arr):
    maxval = 0
    maxarr = {}
    newarr = {}
    for index,value in enumerate(arr):
        maxval = max(value,maxval)
        maxarr[index] = maxval
        newarr[value] = index
    bobwin = False
    while index >= 0:
        maxval = maxarr[index]
        index  = newarr[maxval]-1
        bobwin = not bobwin
    return "BOB" if bobwin else "ANDY"

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    print(gamingArray(arr))

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×