We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Greedy solutions won't necesserily work since reducing the size of the number as much as possible is not always the best move. Instead, using dynamic programming the problem can be solved very efficiently. This is my C++ solution.

intmain(){intmax=1000001;intnums[max];//Initialize arrayfor(inti=0;i<max;++i)nums[i]=-1;nums[0]=0;nums[1]=1;nums[2]=2;nums[3]=3;//Precomputefor(inti=0;i<max;++i){if(nums[i]==-1||nums[i]>(nums[i-1]+1))nums[i]=nums[i-1]+1;for(intj=1;j<=i&&j*i<max;++j)if(nums[j*i]==-1||(nums[i]+1)<nums[j*i])nums[j*i]=nums[i]+1;}//Example for 1st 20//for(int i = 0; i < 21; ++i)//cout << "Min for " << i << " is " << nums[i] << endl;intq;cin>>q;for(inti=0;i<q;++i){intn;cin>>n;cout<<nums[n]<<endl;}return0;}

## Down to Zero II

You are viewing a single comment's thread. Return to all comments →

Greedy solutions won't necesserily work since reducing the size of the number as much as possible is not always the best move. Instead, using dynamic programming the problem can be solved very efficiently. This is my C++ solution.