# 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;

}