You are given a set of n numbers , a key p , a end product q.
You have to convert key p to end product q in minimum number array elements of size n
Whenever you choose an element from the array p gets redefined as p = (p*current_element)%(10^5)
using the above operation p has to be converted to q using minimum elements.
for eg
n = 4 , p = 6 , q = 60
array = [2,5,7,10]
answer here would be 1 since (6*10)%(10^5) = 60 = q.
I thought of a BFS approach to this but as n increases the time becomes exponential how can i reduce the time for this.