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(10^{5})
Expected Space Complexity: O(10^{5})
Constraints:
	1 <= n and n <= 10^{4}
	1 <= arr[i] and arr[i] <= 10^{4}
	1 <= start, end < 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal

Starter code: #User function Template for python3



from typing import List

 

class Solution:

    

    def minimumMultiplications(self, arr : List[int], start : int, end : int) -> int:

        # code here

Solutions:
from typing import List
import collections

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		que = collections.deque()
		que.append((start, 0))
		distance = [float('inf') for _ in range(100000)]
		distance[start] = 0
		while que:
			(currNum, step) = que.popleft()
			for num in arr:
				nextnum = int(currNum * num % 100000)
				if step + 1 < distance[nextnum]:
					que.append((nextnum, step + 1))
					if nextnum == end:
						return step + 1
					distance[nextnum] = step + 1
		return -1


import queue
from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		s = queue.Queue()
		dis = []
		for i in range(0, 10 ** 5):
			dis.append(float('inf'))
		start_count = 0
		s.put([start_count, start])
		while not s.empty():
			(count, node) = s.get()
			if node == end:
				break
			for i in arr:
				t = i * node % 100000
				if count + 1 < dis[t]:
					if t == end:
						return count + 1
					dis[t] = count + 1
					s.put([count + 1, t])
		return -1


from math import inf
from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		queue = []
		queue.append((start, 0))
		visited = [inf for i in range(0, 100000)]
		visited[start] = 0
		mod = 100000
		while queue:
			(node, steps) = queue.pop(0)
			for num in arr:
				temp = node * num % mod
				if steps + 1 < visited[temp]:
					visited[temp] = steps + 1
					if temp == end:
						return steps + 1
					queue.append((temp, steps + 1))
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		queue = []
		queue.append((start, 0))
		distance = [float('inf') for i in range(100000)]
		distance[0] = 0
		mod = 100000
		while queue:
			(node, steps) = queue.pop(0)
			for nums in arr:
				num = node * nums % mod
				if steps + 1 < distance[num]:
					distance[num] = steps + 1
					if num == end:
						return steps + 1
					queue.append((num, steps + 1))
		return -1


from typing import List
from collections import deque
from collections import defaultdict

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = deque([(start, 0)])
		ans = [float('inf')] * 10 ** 5
		ans[0] = 0
		mod = 10 ** 5
		while q:
			(node, step) = q.popleft()
			for i in arr:
				num = i * node % mod
				if num == end:
					return step + 1
				if ans[num] > step + 1:
					ans[num] = step + 1
					q.append((num, step + 1))
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = []
		q.append((start, 0))
		dist = [float('inf') for _ in range(100000)]
		dist[start] = 0
		mod = 100000
		while q:
			(node, steps) = q.pop(0)
			for ele in arr:
				num = int(ele * node) % mod
				if steps + 1 < dist[num]:
					dist[num] = steps + 1
					if num == end:
						return steps + 1
					q.append((num, steps + 1))
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		dist = [float('inf') for i in range(10 ** 5)]
		dist[start] = 0
		mod = 10 ** 5
		queue = [[0, start]]
		while len(queue) > 0:
			(steps, ele) = queue.pop(0)
			for i in arr:
				ans = ele * i % mod
				if steps + 1 < dist[ans]:
					dist[ans] = steps + 1
					queue.append([steps + 1, ans])
				if ans == end:
					return steps + 1
		return -1


from typing import List
from collections import deque
from collections import defaultdict

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = deque()
		ans = [0] * 10 ** 5
		q.append(start)
		visit = [0] * 10 ** 5
		visit[start] = 1
		mod = 10 ** 5
		while q:
			t = q.popleft()
			if t == end:
				return ans[t]
			for i in arr:
				x = t * i % mod
				if visit[x] == 0:
					visit[x] = 1
					q.append(x)
					ans[x] = ans[t] + 1
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = deque()
		dist = [float('inf')] * 100000
		dist[start] = 0
		q.append((0, start))
		while q:
			(steps, node) = q.popleft()
			for i in arr:
				num = i * node % 100000
				if steps + 1 < dist[num]:
					dist[num] = steps + 1
					if num == end:
						return dist[num]
					q.append((steps + 1, num))
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		queue = [(start, 0)]
		n = 999999
		dist = [float('inf')] * n
		dist[start] = 0
		while queue:
			(node, steps) = queue.pop(0)
			for x in arr:
				next_step = steps + 1
				num = x * node % 100000
				if next_step < dist[num]:
					dist[num] = next_step
					if num == end:
						return next_step
					queue.append((num, next_step))
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		steps = [100000] * 100000
		steps[start] = 0
		que = deque([(start, 0)])
		while que:
			(node, step) = que.popleft()
			for num in arr:
				nextNode = node * num % 100000
				if step + 1 < steps[nextNode]:
					steps[nextNode] = step + 1
					if nextNode == end:
						return step + 1
					que.append((nextNode, step + 1))
		return -1


from queue import Queue
from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = []
		ptr = 0
		q.append((0, start))
		cn = 0
		arr = list(filter(lambda x: x > 1, arr))
		mod = 10 ** 5
		dist = [-1] * mod
		dist[start] = 0
		while ptr < len(q):
			node = q[ptr]
			count = node[0]
			product = node[1]
			if product == end:
				return count
			for i in arr:
				new_product = i * product % mod
				if dist[new_product] == -1:
					q.append((count + 1, new_product))
					dist[new_product] += 1
			ptr += 1
		return -1


from typing import List
from collections import deque
import sys

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		queue = deque()
		dist = [sys.maxsize for i in range(100000)]
		queue.append((0, start))
		dist[start] = 0
		while queue:
			(dis, node) = queue.popleft()
			if node == end:
				return dis
			for i in range(len(arr)):
				val = node * arr[i] % 100000
				if dis + 1 < dist[val]:
					dist[val] = dis + 1
					queue.append((dist[val], val))
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		mod = 100000
		queue = []
		dist = [float('inf')] * mod
		queue.append([start, 0])
		while queue:
			(node, dis) = queue.pop(0)
			for i in arr:
				num = i * node % mod
				if dis + 1 < dist[num]:
					dist[num] = dis + 1
					if num == end:
						return dis + 1
					queue.append([num, dis + 1])
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		dist = [float('inf') for _ in range(100001)]
		q = deque([[0, start]])
		dist[start] = 0
		mod = 100000
		while q:
			(steps, node) = q.popleft()
			if node == end:
				return steps
			for nei in arr:
				num = node * nei % mod
				if steps + 1 < dist[num]:
					dist[num] = steps + 1
					q.append([steps + 1, num])
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = []
		q.append((start, 0))
		dist = [9999999999] * 100000
		mod = 100000
		dist[start] = 0
		while q:
			(node, step) = q.pop(0)
			for it in arr:
				num = it * node % mod
				if num == end:
					return step + 1
				if dist[num] > step + 1:
					dist[num] = step + 1
					q.append((num, step + 1))
		return -1


from typing import List
import heapq

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		pq = []
		pq.append((0, start))
		dist = [float('inf')] * 100000
		dist[start] = 0
		while pq:
			(step, u) = heapq.heappop(pq)
			if u == end:
				return step
			for v in arr:
				nx = u * v % 100000
				if dist[nx] > step + 1:
					dist[nx] = step + 1
					heapq.heappush(pq, (step + 1, nx))
		return -1


from typing import List
import heapq
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = deque()
		q.append([0, start])
		dist = [9999999] * 100000
		dist[start] = 0
		while q:
			(d, node) = q.pop()
			if node == end:
				return d
			for el in arr:
				dest = el * node % 100000
				if dist[dest] > d + 1:
					dist[dest] = d + 1
					q.appendleft([d + 1, dest])
		return -1


from typing import List
import heapq

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		hp = []
		dist = [9999999] * 100000
		heapq.heappush(hp, [0, start])
		dist[start] = 0
		while hp:
			(d, node) = heapq.heappop(hp)
			if node == end:
				return d
			for el in arr:
				dest = el * node % 100000
				if dist[dest] > d + 1:
					dist[dest] = d + 1
					heapq.heappush(hp, [d + 1, dest])
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		if start == end:
			return 0
		ans = []
		for i in range(100001):
			ans.append(-1)
		q = deque()
		q.append(start)
		ans[start] = 0
		while len(q) != 0:
			node = q[0]
			q.popleft()
			if node == end:
				return ans[node]
			for i in range(len(arr)):
				mul = node * arr[i]
				mul = mul % 100000
				if ans[mul] == -1:
					ans[mul] = ans[node] + 1
					q.append(mul)
		return -1


import math
from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		queue = deque()
		mod = 100000
		dist = [math.inf] * mod
		dist[start] = 0
		queue.append([start, 0])
		while queue:
			(value, steps) = queue.popleft()
			for i in arr:
				v = value * i % mod
				if v == end:
					return steps + 1
				if steps + 1 < dist[v]:
					queue.append([v, steps + 1])
					dist[v] = steps + 1
		return -1


from typing import List
import heapq

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		dis = [float('inf')] * 10 ** 5
		pq = []
		pq.append((0, start))
		heapq.heapify(pq)
		dis[start] = 0
		while pq:
			(mul, node) = heapq.heappop(pq)
			if node == end:
				return mul
			for i in arr:
				n = node * i % 10 ** 5
				if mul + 1 < dis[n]:
					dis[n] = mul + 1
					heapq.heappush(pq, (dis[n], n))
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		if end > 99999:
			return -1
		dis = [float('inf') for i in range(100000)]
		q = [[start, 0]]
		dis[start] = 0
		while q:
			(val, step) = q.pop(0)
			if val == end:
				return step
			for i in arr:
				new_val = val * i % 100000
				new_step = step + 1
				if new_val == end:
					return new_step
				if dis[new_val] > new_step:
					dis[new_val] = new_step
					q.append([new_val, new_step])
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, a: List[int], start: int, end: int) -> int:
		if start == end:
			return 0
		mod = 100000
		dis = [float('inf')] * 100000
		q = deque([(0, start % mod)])
		dis[start] = 0
		while q:
			(step, node) = q.popleft()
			for i in arr:
				t = i * node % mod
				if step + 1 < dis[t]:
					dis[t] = step + 1
					if t == end:
						return step + 1
					q.append((step + 1, t))
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, a: List[int], start: int, end: int) -> int:
		ans = [float('inf')] * 100000
		mod = 100000
		q = deque()
		q.append(start % mod)
		ans[start] = 0
		while len(q) > 0:
			top = q.popleft()
			if top == end:
				return ans[end]
			for i in arr:
				pushed = top * i % mod
				if ans[top] + 1 < ans[pushed]:
					ans[pushed] = ans[top] + 1
					if pushed == end:
						return ans[pushed]
					q.append(pushed)
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, a: List[int], start: int, end: int) -> int:
		ans = [-1 for i in range(100001)]
		mod = 100000
		q = deque()
		q.append(start % mod)
		ans[start] = 0
		while len(q) > 0:
			top = q.popleft()
			if top == end:
				return ans[end]
			for i in range(n):
				pushed = top * a[i]
				pushed = pushed % mod
				if ans[pushed] == -1:
					ans[pushed] = ans[top] + 1
					q.append(pushed)
		return -1


import heapq
from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		mod = 100000
		dist = [1000000000.0 for _ in range(mod + 1)]
		dist[start] = 0
		pq = []
		heapq.heappush(pq, (0, start))
		while pq:
			(dis, node) = heapq.heappop(pq)
			if dist[end] != 1000000000.0:
				return dist[end]
			for i in arr:
				adjnode = node * i % mod
				if 1 + dis < dist[adjnode]:
					dist[adjnode] = dis + 1
					heapq.heappush(pq, (dis + 1, adjnode))
		return -1


from typing import List
from collections import defaultdict as dict, deque as dq

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		dist = [float('inf') for i in range(10 ** 5)]
		dist[start] = 0
		mod = 10 ** 5

		def bfs():
			q = dq([(start, 0)])
			while q:
				(node, step) = q.popleft()
				if node == end:
					return step
				for num in arr:
					neib = node * num % mod
					neibStep = step + 1
					if neibStep < dist[neib]:
						dist[neib] = neibStep
						q.append((neib, neibStep))
			return -1
		return bfs()


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		marked = [-1] * 100000
		marked[start] = 0
		q = deque()
		q.append(start)
		while len(q) > 0:
			c = q.popleft()
			if c == end:
				return marked[c]
			for a in arr:
				d = c * a % 100000
				if marked[d] == -1:
					marked[d] = marked[c] + 1
					q.append(d)
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		q = [[start, 0]]
		b = [10 ** 9] * 10 ** 5
		b[start] = 0
		mod = 10 ** 5
		while q:
			s = q.pop(0)
			ele = s[0]
			stop = s[1]
			for i in arr:
				if i * ele % mod == end:
					return stop + 1
				if b[ele * i % mod] > stop + 1:
					q.append([ele * i % mod, stop + 1])
					b[ele * i % mod] = stop + 1
		return -1


from queue import PriorityQueue
from typing import List
from sys import maxsize as maxx

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		pq = PriorityQueue()
		q = []
		cost = [maxx for i in range(100000 + 1)]
		q.append((start, 0))
		cost[start] = 0
		while q:
			query = q.pop(0)
			node = query[0]
			st = query[1]
			num = node
			for i in range(len(arr)):
				new_num = num * arr[i]
				if new_num > 100000:
					new_num %= 100000
				if st + 1 < cost[new_num]:
					cost[new_num] = st + 1
					if new_num == end:
						return st + 1
					q.append((new_num, st + 1))
		return -1


from heapq import heappop, heappush
from math import inf
inf = float('inf')
from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		mod = 10 ** 5
		q = []
		q.append((0, start))
		dis = [inf] * 10 ** 5
		dis[start] = 0
		while q:
			(steps, node) = heappop(q)
			if node == end:
				return steps
			for item in arr:
				temp = item * node % mod
				if temp == end:
					return steps + 1
				if dis[temp] > steps + 1:
					heappush(q, (steps + 1, temp))
					dis[temp] = steps + 1
		if dis[end] != inf:
			return dis[end]
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		mod = 100000
		dist = [float('inf') for i in range(mod)]
		dist[start] = 0
		q = deque()
		q.append((0, start))
		while q:
			(step, node) = q.popleft()
			if node == end:
				return step
			for adj in arr:
				newnode = node * adj % mod
				if step + 1 < dist[newnode]:
					dist[newnode] = 1 + step
					q.append((step + 1, newnode))
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		dis = [float('inf')] * 10 ** 5
		dis[start] = 0
		queue = deque([(0, start)])
		while queue:
			(steps, root) = queue.popleft()
			if root == end:
				return steps
			for val in arr:
				num = val * root % 10 ** 5
				if steps + 1 < dis[num]:
					dis[num] = steps + 1
					queue.append((steps + 1, num))
		return -1


from typing import List
from collections import *

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		m = 100000
		visited = set()
		qu = deque([start])
		visited.add(start)
		ans = 0
		while qu:
			l = len(qu)
			for _ in range(l):
				curr = qu.popleft()
				for ele in arr:
					val = ele * curr % m
					if val == end:
						return ans + 1
					if val not in visited:
						visited.add(val)
						qu.append(val)
			ans += 1
		return -1


from typing import List
import sys
from queue import Queue

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		distance = [sys.maxsize] * 100000
		q = Queue()
		q.put((start, 0))
		while not q.empty():
			x = q.get()
			for i in arr:
				num = x[0] * i % 100000
				if x[1] + 1 < distance[num]:
					distance[num] = x[1] + 1
					if num == end:
						return distance[num]
					q.put((num, x[1] + 1))
		return -1


from typing import List
from collections import deque

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		mod = 100000
		queue = deque()
		queue.append([start % mod, 0])
		visited = [float('inf')] * (mod + 1)
		while queue:
			(node, steps) = queue.popleft()
			if node == end:
				return steps
			for num in arr:
				nexti = num * node % mod
				if steps + 1 < visited[nexti]:
					visited[nexti] = steps + 1
					queue.append([nexti, steps + 1])
		return -1


from typing import List

class Solution:

	def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
		mod = 100000
		que = [(start, 0)]
		dist = {start: 0}
		while que:
			(curr, curr_level) = que.pop(0)
			for wt in arr:
				nbr = wt * curr % mod
				if nbr == end:
					return curr_level + 1
				if nbr not in dist or curr_level + 1 < dist[nbr]:
					dist[nbr] = curr_level + 1
					que.append((nbr, curr_level + 1))
		return -1