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

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

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

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