HackerEarth The Witches of HEgwarts! problem solution

In this HackerEarth The Witches of HEgwarts! problem solution Little PandeyG is a curious student, studying in HEgwarts. Being smarter, faster and displaying more zeal for magic than any other student, one by one he managed to impress the three hidden witches of the school. They knew his secret desire to be a warrior, so each of them gave him some super power to use if he's up for a fight against one of his enemies.

The first witch: She gave PandeyG the power to take away one unit of strength away from his enemies. - Eg 36 - 1 = 35.

The second witch: Jealous of the first witch, the second one gave the kid the power to halfen the strength of his enemies. - Eg. 36/2 = 18.

The third witch: Even better, she gave him the power to reduce the strength of his enemies to one third of what it initially was. - Eg. 36/3 = 12.

The witches, though, clearly told him that he'll be only able to use these powers if the strength of the opponent is an integer, otherwise not.

Since, PandeyG is one smart kid, he knew that by using all three of the powers he has got, he'll be able to defeat every enemy he's ever going to face, sometime or the other, in some number of moves.

Now, here's the twist: In spite of having all these powers, PandeyG was still losing matches against his enemies - because he was unable to use them in the optimal fashion. To defeat an opponent, you need to make sure that the enemy has only 1 unit of strength left in him.

Given the value 'k' - k being the units of the enemy of PandeyG's strength, help PandeyG figure out the minimum number of magical hits he'll be needing to defeat his opponent, using his powers.

HackerEarth The Witches of HEgwarts! problem solution.

#include<bits/stdc++.h>
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>

using namespace std;

set < long long int > s;
vector < long long int > v;

int main()
{
    int tc;
    cin>>tc;
    assert(1<=tc);
    assert(tc<=1000);
    while(tc--)
    {
        v.clear(); //Clearing the set, everytime.
        s.clear();//Clearing the vector, everytime.
        
        long long int n;
        int ans=0;
        
        cin>>n;
        assert(1<=n);
        assert(n<=1000000000);
        
        v.push_back(n);
        
        int i=0, f=0, j=1;
        
        while(1)
        {
            if(n==1)
                break;
            if(f==1)
                break;  
            ans+=1;
            
            for(int k=i; k<j; k++)
            {
                int x = -1, y = -1, z = -1;
                if(v[k]%3==0)
                    x=v[k]/3;
                if(v[k]%2==0)
                    y=v[k]/2;
                z=v[k]-1;
                if(x==1 or y==1 or z==1)
                {
                    f=1;
                    break;
                }
                if(x!=-1)
                {
                    if(s.find(x) == s.end())
                    {
                        s.insert(x);
                        v.push_back(x);
                    }
                }
                if(y!=-1)
                {
                    if(s.find(y) == s.end())
                    {
                        s.insert(y);
                        v.push_back(y);
                    }
                }
                if(z!=-1)
                {
                    if(s.find(z) == s.end())
                    {
                        s.insert(z);
                        v.push_back(z);
                    }
                }

            }
            i=j;
            j=v.size();
        }
        cout<<ans<<endl;
    }
    return 0;
}

Second solution

#include <cstdio>
#include <cassert>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

#define MAX 10000000

int moves[MAX];

void pre(){
    moves[1] = 0;
    moves[0] = 1000000001;
    for(int i=2;i<MAX;i++){
        moves[i] = 1+moves[i-1];
        if(i%2==0)
            moves[i] = min(moves[i], moves[i/2]+1);
        if(i%3==0)
            moves[i] = min(moves[i], moves[i/3]+ 1);
    }
    return;
}

int solve(int N){
    int ans;
    if(N<MAX)
        return moves[N];
    else{
        ans = N-1;
        if(N%2==0)
            ans = min(ans, 1+solve(N/2));
        else
            ans = min(ans, 1+solve(N-1));
        if(N%3==0)
            ans = min(ans, 1+solve(N/3));
        else
            ans = min(ans, 1+solve(N-1));
        return ans;
    }
}
int main(){
    int t, N;
    pre();
    scanf("%d",&t);
    assert(t<=1000);
    while(t--){
        scanf("%d", &N);
        assert(N<=1000000000);
        assert(N>0);
        printf("%d\n",solve(N));
    }
    return 0;
}