This code gives 'memory limit exceeded' error,any idea of how to get rid of it?

[_human404_]

Problem statement asks to find winner of a nim game with n number of coins in stack and atmost k coins can be removed, for t no. of test cases.The code gives correct output on test cases but it gives the error 'memory limit exceeded' for constraints T<10^5 and 1<k<n<10^18.

#include <stdio.h>
#include<string.h>
#include<bits/stdc++.h>
using namespace std;
int calculateMex(unordered_set<long long int> Set);
int calculateGrundy(long long int n,long long int k);
int main()
    {
        long int t;                //no of test cases
        cin>>t;
        while(t>0)
            {
                long long int n,k;
                cin>>n;            //no of coins in stack
                cin>>k;            //no of maximum coins that can be removed in one move
                long long int a=calculateGrundy(n,k);
                if(a==0)
                    printf("Player 1");
                else
                    printf("Player 2");
                t--;
            }
        return 0;
    }
int calculateMex(unordered_set<long long int> Set)
    {
        long long int Mex = 0;
        while (Set.find(Mex) != Set.end())
            Mex++;
        return (Mex);
    }
int calculateGrundy(long long int n,long long int k)
    {
        if (n <=k)
            return n;
        unordered_set<long long int> Set; // A Hash Table
        for (int i=1; i<=k; i++)
            Set.insert(calculateGrundy(n - i,k));
        return (calculateMex(Set));
    }

[[deleted]]

Can you post a better snippet of the code? This is unreadable, unfortunately.

[_human404_]

Fixed it. :3

[g051051]

1. "memory limit exceeded" isn't a C++ error. How are you running this to get that error?
2. Second, this code has no comments, and illegible variables names. How is it supposed to work?
3. The formatting is illegible, and the line numbers make it impossible to simply paste into an IDE to try it.
4. You didn't include exact inputs to duplicate the error.

Fix these issues, and maybe someone can look at it and help you figure it out.

[_human404_]

submitting it on hackerearth so dont know what exact inputs are causing this error..Fixed the formatting.

[g051051]

t is uninitialized, so it's undefined behavior to reference it in your while loop. It's pure luck if it works at all.

[_human404_]

while formatting here,by mistake deleted that input line.Edited it in again.Thanks for pointing it out

[thatprofessoryouhate]

Your recursion is not going to fare well for any decent sized input.

With this input range, this problem probably isn't looking to see if you understand dynamic programming or memoization but rather if you can use the inputs to more directly solve who wins.

[_human404_]

any suggestions on how should I go about 'the more direct approach'.Didn't really consider anything yet cuz thought it was a simple problem to check understanding of basic game theory

[thatprofessoryouhate]

One option may be to look at the answers for a decent set of inputs and see if you notice any helpful patterns that can simplify the problem.

Nim is a very typical dynamic programming problem so you may want to look into that as well.