Problem Link:
Author - Yash Dwivedi
Tester - Shubham Kushwaha
Editorialist - Yash Dwivedi
Difficulty :
Easy
PREREQUISITES:
Dynamic programming
Problem :
Given a number n in one move you can either divide it by 5(if n%5==0) or subtract it by 3. You need to determine the minimum number of moves to make the n equal to 2, if this is not possible print -1.
Explanation
It was a simple dp problem where first you would precompute all the answers and then if answer is infinity then print no else print the answer.
Check if the i-th number is infinity then move to the next number otherwise compute the answer for i for i*5 and i+3 and store the minimum one.
Solution
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int ans[1000001];
int main()
{
for(int i=1;i<=1000000;i++){
ans[i] = 1e9;
}
ans[2] = 0;
for(int i=2;i<=1000000;i++){
if(ans[i]==1e9)
continue;
if(i*5<=1000000){
ans[i*5] = min(ans[i*5], ans[i] + 1);
}
if(i+3<=1000000){
ans[i+3] = min(ans[i+3], ans[i] + 1);
}
}
int t;
cin>>t;
while(t–)
{
int x;
cin>>x;
if(ans[x] == 1e9)
cout<<“-1\n”;
else cout<<ans[n]<<“\n”;
}
return 0;
}