HELP WITH BYTELANDIAN GOLD COINS

1

I TRIED USING RECURSION
I HAVE PASSED ALL THE TEST CASES STILL WA
BELOW IS MY CODE
THE RECURSION FUNCTION IS SUPPOSED TO RETURN MAXIMUM AMERICAN DOLLARS FOR THE COIN IN HAND

        #include <iostream>
        using namespace std;
        #define ll long long 
        ll int mad(ll int n);

        int main()
        {
          int t;
          cin>>t;
          while(t--)
          {
          	ll int n;
          	cin>>n;
          	cout<<mad(n)<<endl;

          }

        	return 0;
        }

        ll int mad(ll int n)
        {
        	
        if(n==1)
        {
        	return 1;
        }
        if(n==2)
        {
        	return 2;
        }
        if(n==0)
        {
        	return 0;
        }



          if(mad(n/2)+mad(n/3)+mad(n/4)>n)
          {
          	return mad(n/2)+mad(n/3)+mad(n/4);
          }
          else
          {
          	return n;
          }


        }
2

It doesn’t give you the number of testcases, you have to input until you reach the end of file, as in

while(cin>>n){
     // code here
}

Also your code is slow. About O(n^{1.1})

3

ok got it thanks.
could you also tell me how did u calculate the time complexity in this case

4

A map would reduce your time complexity to O(log^3 n). Use a map to store precomputed values.
Edit: Misread the question.
Let T(n) denote the time taken for input n
T(n)=T(n/2)+T(n/3)+T(n/4) + O(1)
Let the time complexity be O(n^x). I’m not sure how to figure out this part objectively, but you have to figure out the form.
Therefore
n^x = (n/2)^x + (n/3)^x + (n/4)^x + 1
Let us neglect 1, as it is negligible in this case, and divide by n^x
We get
1^x = (1/2)^x + (1/3)^x + (1/4)^x
solving for x, we get x=1.08.
A little bit is not objective, but is obvious.

1 Like