HackerRank Stone Division problem solution

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.

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