Given start, end and an array arr of n numbers. At each step, start is multiplied with any number in the array and then mod operation with 100000 is done to get the new start.

Your task is to find the minimum steps in which end can be achieved starting from start. If it is not possible to reach end, then return -1.

n<=1e4, arr[i]<=1e4, start, end<1e5

Expected Time & Space Complexity : O(1e5)

class Solution {
  public:
    int minimumMultiplications(vector<int>& v, int s, int d) {
        int n = v.size();
        int MOD = 1e5;
        queue<pair<int,int>>q; q.push({s,0});
        vector<int>vis(1e5); vis[s]=1;
        while(!q.empty()){
            auto elem = q.front(); q.pop();
            int i = elem.first; int res = elem.second;
            if(i==d) return res;
            for(int j=0;j<n;j++){
                int val = (i*v[j])%MOD;
                if(!vis[val]) {
                    vis[val] = 1;
                    q.push({val,res+1});
                }
            }
        }
        return -1;
    }
};