Can someone explain this code.

Can somebody explain this code :

Problem link
Solution link

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll arr[100005];
ll dp(ll n)
{
    if(n < 10000)  return arr[n];
    return max(n, dp(floor(n/2)) + dp(floor(n/3)) + dp(floor(n/4)));
}
int main()
{
        ll n;
        while(scanf("%lld",&n)!=EOF){
            arr[0] = 0;
            arr[1] = 1;
            for(ll i = 2; i <= 100000; i++){
                ll a = floor(i/2), b = floor(i/3), c = floor(i/4);
                arr[i] = max(arr[a]+arr[b]+arr[c], i);
            }
            cout<<dp(n)<<endl;
        }
}

This code is written by me so I guess I can explain this one though this isn’t the best implementation to solve this problem and I’ve overcomplicated things here.
In this problem we just need to calculate the optimal exchange rate for the coins which can easily be solved using Dynamic Programming. In this code I store the results of the exchange rate in the array arr. The base case here is 0 for 0 coins and 1 for 1 coin. Using the base cases I have calculated the optimal values for all numbers in the given constraints range. Now I can just answer each query in O(1) time.
The function dp() is irrelevant here though, I was initially going for a memoized solution but then I just mixed the two approaches and thus it got messed up a little. The corrected code would look something like below code. I moved the for loop outside the while loop so that the precomputation takes place only once and also removed the not required function.

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll arr[100005];
int main()
{
        ll n;
        arr[0] = 0;
        arr[1] = 1;
        for(ll i = 2; i <= 100000; i++){
            ll a = floor(i/2), b = floor(i/3), c = floor(i/4);
            arr[i] = max(arr[a]+arr[b]+arr[c], i);
        }
        while(scanf("%lld",&n)!=EOF){
            
            cout<<arr[n]<<endl;
        }
}
1 Like

But What if N is 10^9 ? For N=12 Your code is giving 12 a O/P. WA!

No

His solution is giving 13.

PS: @rinem Your implementation is not at all complicated, but very neat approach. I liked it

@guitarlover I don’t know if my code would work if N is 10^9 but usually the constraints are not that high
@taran_1407 Thank You!

Not the answer but you may look at this for easy implementation.