In this HackerRank Gaming Array 1 problem-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.
In a single move, a player chooses the maximum element in the array. He removes it and all elements to its right. For example, if the starting array arr = [2,3,5,4,1], then it becomes arr = [2,3] after removing [5,4,1].
The two players alternate turns.
The last player who can make a move wins.
Andy and Bob play g 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.
Problem solution in Python.
#!/bin/python3 import math import os import random import re import sys # # Complete the 'gamingArray' function below. # # The function is expected to return a STRING. # The function accepts INTEGER_ARRAY arr as parameter. # def gamingArray(arr): # Write your code here current_max = 0 count = 0 for element in arr: if element > current_max: count += 1 current_max = element if count % 2 ==1: return "BOB" else: return "ANDY" if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') g = int(input().strip()) for g_itr in range(g): arr_count = int(input().strip()) arr = list(map(int, input().rstrip().split())) result = gamingArray(arr) fptr.write(result + 'n') fptr.close()
Problem solution in Java.
import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; class Result { public static String gamingArray(List<Integer> arr) { if(arr.size()==1) return "BOB"; if(arr.size()==2) { if(arr.get(0)<arr.get(1)) return "ANDY"; else return "BOB"; } int max = Collections.max(arr); int cur = arr.get(0); int count = 0; for(int i=1; cur!=max; i++ ){ if(cur<arr.get(i)) { cur = arr.get(i); count++; } } if(count%2!=0) return "ANDY"; return "BOB"; } } public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int g = Integer.parseInt(bufferedReader.readLine().trim()); IntStream.range(0, g).forEach(gItr -> { try { int arrCount = Integer.parseInt(bufferedReader.readLine().trim()); List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\s+$", "").split(" ")) .map(Integer::parseInt) .collect(toList()); String result = Result.gamingArray(arr); bufferedWriter.write(result); bufferedWriter.newLine(); } catch (IOException ex) { throw new RuntimeException(ex); } }); bufferedReader.close(); bufferedWriter.close(); } }
Problem solution in C++.
#include <bits/stdc++.h> using namespace std; string ltrim(const string &); string rtrim(const string &); vector<string> split(const string &); /* * Complete the 'gamingArray' function below. * * The function is expected to return a STRING. * The function accepts INTEGER_ARRAY arr as parameter. */ string gamingArray(vector<int> arr) { map<int, int> m; int len = arr.size(); for (int i = 0; i < len; ++i) { m[arr[i]] = i; } int cur_index = len; int round = 0; for (auto it = m.rbegin(); it != m.rend(); it++) { if (it->second < cur_index) { cur_index = it->second; ++round; } } return round % 2 == 0 ? "ANDY" : "BOB"; } int main() { ofstream fout(getenv("OUTPUT_PATH")); string g_temp; getline(cin, g_temp); int g = stoi(ltrim(rtrim(g_temp))); for (int g_itr = 0; g_itr < g; g_itr++) { string arr_count_temp; getline(cin, arr_count_temp); int arr_count = stoi(ltrim(rtrim(arr_count_temp))); string arr_temp_temp; getline(cin, arr_temp_temp); vector<string> arr_temp = split(rtrim(arr_temp_temp)); vector<int> arr(arr_count); for (int i = 0; i < arr_count; i++) { int arr_item = stoi(arr_temp[i]); arr[i] = arr_item; } string result = gamingArray(arr); fout << result << "n"; } fout.close(); return 0; } string ltrim(const string &str) { string s(str); s.erase( s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace))) ); return s; } string rtrim(const string &str) { string s(str); s.erase( find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(), s.end() ); return s; } vector<string> split(const string &str) { vector<string> tokens; string::size_type start = 0; string::size_type end = 0; while ((end = str.find(" ", start)) != string::npos) { tokens.push_back(str.substr(start, end - start)); start = end + 1; } tokens.push_back(str.substr(start)); return tokens; }
Problem solution in C.
#include <assert.h> #include <ctype.h> #include <limits.h> #include <math.h> #include <stdbool.h> #include <stddef.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> char* readline(); char* ltrim(char*); char* rtrim(char*); char** split_string(char*); int parse_int(char*); /* * Complete the 'gamingArray' function below. * * The function is expected to return a STRING. * The function accepts INTEGER_ARRAY arr as parameter. */ int findMax(int *arr, int count) { int max = arr[0]; int maxi = 0; int c = 1; for (int i =0; i<count;i++) { if (arr[i] > max) { max = arr[i]; maxi = i; c++; } } return c; } char* gamingArray(int arr_count, int* arr) { char *a = "ANDY"; char *b = "BOB"; int size = arr_count; int c = 0; c = findMax(arr, size); printf("n%d",c); return (c%2?b:a); } int main() { FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w"); int g = parse_int(ltrim(rtrim(readline()))); for (int g_itr = 0; g_itr < g; g_itr++) { int arr_count = parse_int(ltrim(rtrim(readline()))); char** arr_temp = split_string(rtrim(readline())); int* arr = malloc(arr_count * sizeof(int)); for (int i = 0; i < arr_count; i++) { int arr_item = parse_int(*(arr_temp + i)); *(arr + i) = arr_item; } char* result = gamingArray(arr_count, arr); fprintf(fptr, "%sn", result); } fclose(fptr); return 0; } char* readline() { size_t alloc_length = 1024; size_t data_length = 0; char* data = malloc(alloc_length); while (true) { char* cursor = data + data_length; char* line = fgets(cursor, alloc_length - data_length, stdin); if (!line) { break; } data_length += strlen(cursor); if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; } alloc_length <<= 1; data = realloc(data, alloc_length); if (!data) { data = ' '; break; } } if (data[data_length - 1] == 'n') { data[data_length - 1] = ' '; data = realloc(data, data_length); if (!data) { data = ' '; } } else { data = realloc(data, data_length + 1); if (!data) { data = ' '; } else { data[data_length] = ' '; } } return data; } char* ltrim(char* str) { if (!str) { return ' '; } if (!*str) { return str; } while (*str != ' ' && isspace(*str)) { str++; } return str; } char* rtrim(char* str) { if (!str) { return ' '; } if (!*str) { return str; } char* end = str + strlen(str) - 1; while (end >= str && isspace(*end)) { end--; } *(end + 1) = ' '; return str; } char** split_string(char* str) { char** splits = NULL; char* token = strtok(str, " "); int spaces = 0; while (token) { splits = realloc(splits, sizeof(char*) * ++spaces); if (!splits) { return splits; } splits[spaces - 1] = token; token = strtok(NULL, " "); } return splits; } int parse_int(char* str) { char* endptr; int value = strtol(str, &endptr, 10); if (endptr == str || *endptr != ' ') { exit(EXIT_FAILURE); } return value; }