## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# An interesting game challenge

Sharing is caring!

Problem statement
Andy loves playing games. He wants to play a game with his little brother, Bob, using an array, $A$, of $n$ distinct integers. 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 $A = \left[2,3,5,4,1\right]$, then it becomes $A = \left[2,3\right]$ after the first move because we remove the maximum element (i.e., $5$) and all elements to its right (i.e., $4$ and $1$).
• 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 $g$ games. Given the initial array for each game, can you find and print the name of the winner on a new line? If Andy wins, print ANDY; if Bob wins, print BOB.

Input Format
The first line contains a single integer denoting $g$ (the number of games). The $2\times g$ subsequent lines describe each game array over two lines:

1. The first line contains a single integer, $n$, denoting the number of elements in $A$.
2. The second line contains $n$ distinct space-separated integers describing the respective values of $a_0, a_1, \dots, a_{n-1}$ for array $A$.

Constraints
Array contains $n$ distinct integers. $1 \le g \le 100$ $1 \le n \le 10^5$ $1 \le a_i \le 10^9$
The sum of $n$ over all games does not exceed $10^5$.

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:

1.
Initially, the array looks like this: In the first move, Bob removes $6$ and all the elements to its right, resulting in $A = \left[5,2\right]$: In the second move, Andy removes $5$ and all the elements to its right, resulting in $A = \left[\right]$: 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.

2.
In the first move, Bob removes $3$ and all the elements to its right, resulting in $A = \left[\right]$. 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.

Solution

public class AnInterestingGame {
private static final String BOB = "BOB";
private static final String ANDY = "ANDY";

private static void solve(int[] a, int start, int end, String player) {
if (start > end) {
System.out.println(player.equals(BOB) ? ANDY : BOB);
} else {
int max = Integer.MIN_VALUE;
int maxIdx = -1;
for (int i = start; i <= end; i++) {
if (a[i] > max) {
max = a[i];
maxIdx = i;
}
}

solve(a, start, maxIdx - 1, player.equals(BOB) ? ANDY : BOB);
}

}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);
int games = in.nextInt();
for (int g = 0; g < games; g++) {
int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}

solve(a, 0, a.length - 1, BOB);
}
}
}