Minimum multiplication to reach end

The problem took me overall 46 mins including the coding part.

This problem was quite confusing considering the fact that it took me around 20 mins to get to the conclusion, that my overall approach was wrong, as it is based on the bfs approach, whereas I was trynna go with the subsequence recursive equations approach. The worst part is that I even ignored the fact somehow that the recursive approach would not be under the Time Limit specified. 

Maybe that was because the question was very much like a "take this or ignore this" type, which usually I have solved using the recursive approach with a DP.

Well, when I garnered about the bfs then the concepts were quite apparent.

The bfs approach, simply says...we gotta check for every possible case and every possibility, and to do that we are gonna use a queue, we'll put any element that is yet not "explored" in the queue for exploration( just like we explore a graph, that's why the name BFS ). 

                                                                               Right...

Then also make sure that we don't put an elem that has already been explored, so for that what's the logic?

We maintain an array for that( which is gonna tell us whether an elem is yet explored or not? ), and a little bit tricky part here is that I have used the array to even keep the answer of the test case. 

Means the array will contain the "Minimum number of operations that were required to get to the end".

Just take the simple example of 1st Sample Test Case, 

We start with 3, so 3 is now explored and will keep 0 in 3rd index, then will check 3 with every possible number, 2, 5 and 7,

so the possible, multiples are 6, 15, and 21. Now these are not yet explored( remember only 3 explored...) so let's put these to exploration queue, so exploration queue is [6,15,21] currently.

Also, with these values will keep the counts, 1, 1 and 1, cause this is the 2nd operation, and this was concluded because the previous elem 3 had 0 with it, so +1.

Note, we'll keep exploring till the exploration queue is not empty, or if we get the result, then just return.

Next gotta explore 6, so 6 with all possibilities, 2,5 and 7, we get 12, 30, and here we see that 30 is the required value, so just return, the value in 6 is 1, and bcz of this the value in 30 is 1+1, that is 2.

So, required 2 operations, that is 1st: 3*2=6, 2nd: 6*5=30.

The problem statement is quite self-explanatory and the overall logic can only be understood, when we dry run the test cases, by ourself. Overall this was a medium level problem. with time complexity O((10^5)n) cause we are just looping n times, for 10^5 times.

Problem Statement: 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.

Example 1:

Input:
arr[] = {2, 5, 7}
start = 3, end = 30
Output:
2
Explanation:
Step 1: 3*2 = 6 % 100000 = 6 
Step 2: 6*5 = 30 % 100000 = 30

Example 2:

Input:
arr[] = {3, 4, 65}
start = 7, end = 66175
Output:
4
Explanation:
Step 1: 7*3 = 21 % 100000 = 21 
Step 2: 21*3 = 63 % 100000 = 63 
Step 3: 63*65 = 4095 % 100000 = 4095 
Step 4: 4095*65 = 266175 % 100000 = 66175

Your Task:
You don't need to print or input anything. Complete the function minimumMultiplications() which takes an integer array arr, an integer start and an integer end as the input parameters and returns an integer, denoting the minumum steps to reach in which end can be achieved starting from start.

Expected Time Complexity: O(105)
Expected Space Complexity: O(105)

Constraints:

• 1 <= n <= 104
• 1 <= arr[i] <= 104
• 1 <= start, end < 105

Python Implementation:-

def minimumMultiplications(self, arr, start, end):

        # code here

        if(start==end):

            return 0

           

        dp=[-1]*100000

        queue=[]

       

        dp[start]=0

        queue.append(start)

       

        while(len(queue)!=0):

            elem=queue[0]

            queue.pop(0)

           

            for i in range(len(arr)):

                mul=(elem*arr[i])%100000

               

                if(dp[mul]==-1):

                    queue.append(mul)

                    dp[mul]=dp[elem]+1    

                   

                    if(mul==end):

                        return dp[mul]

                       

        return -1