Min Operations to One
JavaScript
Hard
3 views
Problem Description
You can do operations: n=n-1, if n%2==0 n=n/2, if n%3==0 n=n/3. Find minimum steps to make n to 1.
Input Format
One integer n.
Output Format
One integer min steps.
Official Solution
const fs=require('fs');const s=fs.readFileSync(0,'utf8').trim();if(!s)process.exit(0);const n=Number(s);let dp=new Int32Array(n+1);dp[1]=0;for(let i=2;i<=n;i++){let best=dp[i-1]+1;if(i%2===0)best=Math.min(best,dp[i/2]+1);if(i%3===0)best=Math.min(best,dp[i/3]+1);dp[i]=best;}process.stdout.write(String(dp[n]));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!