In this HackerRank The Prime Game problem solution Manasa loves the nim game, in which there are N buckets, each having Ai balls. Two players play alternately. Each turn consists of removing some non-zero number of balls from one of the buckets. A player with a lack of moves loses. But, Manasa having played it so many times, gets bored one day. So she wants to change the rules of the game. She loves prime numbers, so she makes a new rule: any player can only remove a prime number of balls from a bucket. But there are infinite number prime numbers. So to keep the game simple, a player can only remove X balls from a bucket if X belongs to the set

The whole game can now be described as follows:

There are N buckets, and the Kth bucket contains Ak balls. A player can choose a bucket and remove X balls from that bucket where X belongs to S. A player loses if there are no more available moves.

Manasa plays the first move against Sandy. Who will win if both of them play optimally?

HackerRank The Prime Game problem solution


Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# 2, 3, 5, 7, 11, 13
values = [0, 0, 1, 1, 2, 2, 3, 3, 4]
    
def winner(A):
    nimber = 0  # or grundy number  
    for ak in A:
        nimber ^= values[ak % len(values)];

    return "Manasa" if nimber > 0 else "Sandy"

for _ in range(int(input())):
    input(), print(winner(list(map(int, input().split()))))


Problem solution in Java.

import java.io.*;  
import java.util.*;  
import java.text.*;  
import java.math.*;  
import java.util.regex.*;  

public class Solution {  

    public static void main(String[] args) {  
        int t = ni();  
        for(int i=0; i<t; i++){  
            System.out.println(solve());  
        }  
    }  

    public static int[] values = new int[]{0, 0, 1, 1, 2, 2, 3, 3, 4};  
    public static String solve(){  
        int n = ni();  
        long ak;  
        long nimber = 0; //or grundy number  
        for(int i=0; i<n; i++){  
            ak = nl();  
            nimber ^= values[(int) (ak % values.length)];
        }  
        if(nimber > 0) return "Manasa";  
        return "Sandy";  
    }  

    public static Scanner sc = new Scanner(System.in);  
    public static int ni(){  
        return sc.nextInt();  
    }  
    public static long nl(){  
        return sc.nextLong();  
    }  
}  


Problem solution in C++.

#include <cstdio>

using namespace std;

using int64 = long long;

int ans[9] = {0, 0, 1, 1, 2, 2, 3, 3, 4};

int main() {
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    int n;
    scanf("%d", &n);
    int ret = 0;
    for (int i = 0; i < n; ++i) {
      int64 x;
      scanf("%lld", &x);
      ret ^= ans[x % 9];
    }
    puts(ret ? "Manasa" : "Sandy");
  }
  return 0;
}


Problem solution in C.

#include<stdio.h>
int main()
{    
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        int val = 0;
        long long tmp;
        for( int i = 0 ; i < n ; i++ )
        {
            scanf("%lld", &tmp);
            val = val ^ ( ( tmp % 9 ) / 2 );
        }
        printf("%s\n", val ? "Manasa" : "Sandy");
    }
    return 0;
}