# HackerEarth Movement in arrays problem solution

In this HackerEarth Movement in arrays problem solution Consider an array A of size N. You start from the index 0 and your goal is to reach index N - 1 in exactly M moves.

At any index, you can move forward or backward by a number of steps that is equal to a prime divisor of the value which exists at that index. You cannot go beyond the array while going forward or backward.

Write a program to determine whether it is possible to reach index N - 1 in M moves.

## HackerEarth Movement in arrays problem solution.

`#include<bits/stdc++.h>using namespace std;vector<vector<bool> > multiply(vector<vector<bool> > a,vector<vector<bool> > b) {    int i,j,k;    int r1=a.size();    int r2=b.size();    int c1=a[0].size();    int c2=b[0].size();        vector<vector<bool> > c(r1,vector<bool> (c2));    for(i=0;i<r1;i++)      {        for(j=0;j<c2;j++)          {            for(k=0;k<r2;k++)              {                 if(a[i][k]&&b[k][j])                    c[i][j]=true;              }          }      }    return c; }vector<vector<bool> > pow(vector<vector<bool> > a,long long n)  {    if(n==0)      {        assert(0);        return a;      }    if(n==1)      return a;    vector<vector<bool> > b=pow(a,n/2);    b=multiply(b,b);    if(n%2)      b=multiply(a,b);    return b;  }vector<int> getFactors(int x) {    vector<int> fact;        if(x%2==0)         {            fact.push_back(2);            while(x%2==0)                x/=2;           }    for(int i=3;i*i<=x;i+=2)     {        if(x%i==0)         {            fact.push_back(i);            while(x%i==0)                x/=i;           }     }     if(x!=1)        fact.push_back(x);    return fact; }void eval(){    int n;    cin>>n;    vector<int> a(n);    for(int i=0;i<n;i++)        cin>>a[i];    int moves;    cin>>moves;        vector<vector<bool> > mat(n, vector<bool>(n));    vector<vector<bool> > graph(1, vector<bool>(n));    graph[0][0]=1;        for(int i=0;i<n-1;i++)     {        vector<int> factors = getFactors(a[i]);        for(int j=0;j<factors.size();j++)            {                int x = factors[j];                if(i-x>=0)                    mat[i][i-x]=1;                if(i+x<n)   //less than n-1                    mat[i][i+x]=1;            }     }    mat = pow(mat, moves);    graph = multiply(graph,mat);    if(graph[0][n-1]==1)        cout<<"YES\n";    else        cout<<"NO\n";}int main(){    int t;    cin>>t;    while(t--)      {        eval();     }}`

### Second solution

`#include<bits/stdc++.h>using namespace std;#define rep(i,n) for(i=0;i<n;i++)#define ll long long#define elif else if#define pii pair<ll int,ll int>#define mp make_pair#define pb push_backvector<int>v;int mv,n;vector<vector<int> > mul(vector<vector<int> > a,vector<vector<int> > b) {    int i,j,k,r=a[0].size(),c=a.size();    vector< vector<int> > ans(r);    for(i=0;i<r;i++)      {        ans[i].resize(c,0);        for(j=0;j<c;j++)          {            for(k=0;k<r;k++)                ans[i][j]+= a[i][k]*b[k][j];          }      }    return ans; } vector<vector< int > > mat_pow(vector<vector< int > > mat,int n)  {    if(n==1)      return mat;    vector<vector< int > > ans=mat_pow(mat,n/2);    ans=mul(ans,ans);    if(n%2)      ans=mul(mat,ans);    return ans;  }int foo(){    int i,j;    vector<vector< int > > mat(n);    for(i=0;i<n;i++)    {        mat[i].resize(n,0);        int fac;        fac=2;        if(v[i]%fac==0)        {            if(i+fac<n)                mat[i][i+fac]=1;            if(i-fac>=0)                mat[i][i-fac]=1;            while(v[i]%fac==0)                v[i]/=fac;        }        for(fac=3;fac*fac<=v[i];fac+=2)        {            if(v[i]%fac==0)            {                if(i+fac<n)                    mat[i][i+fac]=1;                if(i-fac>=0)                    mat[i][i-fac]=1;                while(v[i]%fac==0)                    v[i]/=fac;            }        }        if(v[i]>1)        {            fac=v[i];            if(i+fac<n)                mat[i][i+fac]=1;            if(i-fac>=0)                mat[i][i-fac]=1;        }    }    mat= mat_pow(mat,mv);    return mat[0][n-1];}int main(){    int t;    cin>>t;    assert( t>=1 && t<=10);    while(t--)    {        int i,j,m;        cin>>n;        assert( n>=2 && n<=40);        v.clear();        v.resize(n);        rep(i,n){            cin>>v[i];            assert( v[i]>=1 && v[i]<=1000000);        }        cin>>mv;        assert( mv>=1 && mv<=1000000);        if(foo())            cout<<"YES\n";        else            cout<<"NO\n";    }    return 0;}`