Exchange coin problem

#1

#include
#include
#include
using namespace std;

int v[1000000009];
// v[0] = 0;
// v[1] = 1;
int exchange(int n){
if(n==1 ||n==0){
return n;
}

if(v[n]!=0){
    return v[n];
}

int ans1 = exchange(n/2);
int ans2 = exchange(n/3);
int ans3 = exchange(n/4);

int result = ans1+ans2+ans3;
if(result >n){
    v[n] = result;
    return result;
}else{
    v[n] = n;
    return n;
}

}

int main() {

int n;
cin>>n;
cout<<exchange(n)<<endl;
// vector<int> v;
// cout<<v.max_size();

}

weird type error is coming… i know i cannot create an array of 1000000009 type but then how can i do the problem as constraints are strict

#2

You can think of hashmap for this kind of problems.Ask me if you need further help in implementation.

#3

i got it n should be long long here i used int!