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);
        }
    }
}