In this HackerRank Stone Division problem solution we have given the value of N piles of stones, M distinct integers, and the contents of S, find and print the winner of the game. If first wins, print First, otherwise print Second.

HackerRank Stone Division problem solution


Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys


def stoneDivision(n, s):
    if len([q for q in s if n%q==0 and q%2==0])>0:
        return "First"
    fulldata={}
    queue=[n]
    start=0
    while start<len(queue):
        if queue[start] not in fulldata:
            fulldata[queue[start]]=[queue[start]//q for q in s if queue[start]%q==0 and q>1]
            queue=queue+fulldata[queue[start]]
        start+=1
    funct={}
    for gg in sorted(fulldata.keys()):
        funct[gg]=1-min(map(lambda g:funct[g],fulldata[gg]),default=1)
    return "First" if funct[n]%2 else "Second"
            
        

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    n = int(first_multiple_input[0])

    m = int(first_multiple_input[1])

    s = list(map(int, input().rstrip().split()))

    result = stoneDivision(n, s)

    fptr.write(result + '\n')

    fptr.close()


Problem solution in Java.

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

public class Solution {
    public static long zero = 0L;
    
    static int findMex(HashSet<Integer> grundys){
        int mex = 0;
        while(grundys.contains(mex)){
            mex++;
        }
        return mex;
    }
    
    
    static int getGrundy(long n, long[] s, Hashtable<Long, Integer> grundyVals){
       
        if (n == zero){
            return 0;
        }
        else if (grundyVals.containsKey(n)){
            return grundyVals.get(n);
        }
        else{
            HashSet<Integer>nextPositions = new HashSet<Integer>();
            for (int i = 0; i < s.length; i++){
                if (n % s[i] == zero){
                    long pilesize = n/s[i];
                    int g = 0;
                    if(s[i]%2L != 0L){
                        g = getGrundy(pilesize, s, grundyVals);
                    }
                    
                    nextPositions.add(g);
                }
            }
            if(nextPositions.isEmpty()){
                return 0;
            }
            else{
                int mex = findMex(nextPositions);
                grundyVals.put(n, mex);
                return mex;
            }
        }
    }
    
    static String stoneDivision(long n, long[] s) {
        
        Hashtable<Long, Integer> grundyVals = new Hashtable<Long, Integer>();
        Arrays.sort(s);

        
        int grundy_val = getGrundy(n, s, grundyVals);
        if (grundy_val == 0){
            return new String("Second");
        }
        else{
            return new String("First");
        }
       
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] nm = scanner.nextLine().split(" ");

        long n = Long.parseLong(nm[0].trim());

        int m = Integer.parseInt(nm[1].trim());

        long[] s = new long[m];

        String[] sItems = scanner.nextLine().split(" ");

        for (int sItr = 0; sItr < m; sItr++) {
            long sItem = Long.parseLong(sItems[sItr].trim());
            s[sItr] = sItem;
        }

        String result = stoneDivision(n, s);

        bufferedWriter.write(result);
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}


Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long ll;
vector<ll> S;

bool isEnd(ll n) {
    for (ll si : S)
        if (n % si == 0)
            return false;
    return true;
}

unordered_map<ll, bool> saved;

bool stoneDivision(bool fTurn, ll n) {
    if (saved.find(n+n*fTurn) != saved.end())
        return saved[n+n*fTurn];
    
    bool newTurn;
    for (ll si : S) {
        bool fTurnSi = fTurn;
        if (n % si == 0) {
            fTurnSi = !fTurnSi;
            if (stoneDivision(fTurnSi, n / si) == !fTurnSi && si % 2 == 1)
                fTurnSi = !fTurnSi;
        }
        if (fTurnSi == !fTurn) {
            saved[n+n*fTurn] = !fTurn;
            return !fTurn;
        }
    }
    saved[n+n*fTurn] = fTurn;
    return fTurn;
}

int main() {
    ll n, m;
    cin >> n >> m;
    S.resize(m);
    for (int i = 0; i < m; i++)
        cin >> S[i];
    cout << (stoneDivision(true, n) ? "Second" : "First");
    return 0;
}


Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);


char* stoneDivision(long n, int s_count, long* s) {
    int sorts[s_count];
    for(int i = 0; i < s_count; i++){
        sorts[i] = s[i];
    }
    for(int i = 0; i < s_count; i++){
        for(int j = i + 1; j < s_count; j++){
            if(sorts[i] > sorts[j]){
                int temp = sorts[i];
                sorts[i] = sorts[j];
                sorts[j] = temp;
            }
        }
    }

    long *factors = NULL;
    int numfactors = 0;
    long *factorqueue = malloc(sizeof(long));
    factorqueue[0] = n;
    int queuesize = 1;
    int queuedone = 0;
    while(queuedone < queuesize){
        long nextfactor = factorqueue[queuedone];
        if(n%nextfactor == 0){
            int isinlist = 0;
            for(int i = 0; i < numfactors; i++){
                if(factors[i] == nextfactor){
                    isinlist = 1;
                }
            }
            if(isinlist == 0){
                numfactors += 1;
                factors = realloc(factors, numfactors*sizeof(long));
                factors[numfactors - 1] = nextfactor;

                for(int i = 0; i < s_count; i++){
                    if(nextfactor%sorts[i] == 0){
                        queuesize += 1;
                        factorqueue = realloc(factorqueue, queuesize*sizeof(long));
                        factorqueue[queuesize - 1] = nextfactor/sorts[i];
                    }
                }
            }
        }
        queuedone++;
    }

    for(int i = 0; i < numfactors; i++){
        for(int j = i + 1; j < numfactors; j++){
            if(factors[i] > factors[j]){
                long temp = factors[i];
                factors[i] = factors[j];
                factors[j] = temp;
            }
        }
    }

    int factornim[numfactors];
    for(int i = 0; i < numfactors; i++){
        long currfactor = factors[i];
        int issubnim[s_count];
        for(int j = 0; j < s_count; j++){
            issubnim[j] = 0;
        }
        for(int j = 0; j < s_count; j++){
            int jnimval = -1;
            for(int k = 0; k < i; k++){
                if(factors[k]*sorts[j] == currfactor){
                    if(factors[k]%2 == 1){
                        jnimval = factornim[k];
                    }
                    else{
                        jnimval = 0;
                    }
                }
            }
            if(jnimval != -1){
                issubnim[jnimval] = 1;
            }
        }

        int mexval = 0;
        while(issubnim[mexval] == 1){
            mexval++;
        }
        factornim[i] = mexval;
    }

    for(int i = 0; i < numfactors; i++){
        printf("%ld\t", factors[i]);
    }
    printf("\n");
    for(int i = 0; i < numfactors; i++){
        printf("%d\t", factornim[i]);
    }
    printf("\n");

    int nimval = factornim[numfactors - 1];
    if(nimval == 0){
        return "Second";
    }
    else{
        return "First";
    }
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char** nm = split_string(readline());

    char* n_endptr;
    char* n_str = nm[0];
    long n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    char* m_endptr;
    char* m_str = nm[1];
    int m = strtol(m_str, &m_endptr, 10);

    if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }

    char** s_temp = split_string(readline());

    long s[m];

    for (int s_itr = 0; s_itr < m; s_itr++) {
        char* s_item_endptr;
        char* s_item_str = s_temp[s_itr];
        long s_item = strtol(s_item_str, &s_item_endptr, 10);

        if (s_item_endptr == s_item_str || *s_item_endptr != '\0') { exit(EXIT_FAILURE); }

        s[s_itr] = s_item;
    }

    char* result = stoneDivision(n, m, s);

    fprintf(fptr, "%s\n", 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; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }
    if(data[data_length - 1] != '\0'){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

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