Это видео недоступно.
Сожалеем об этом.
G-39. Minimum Multiplications to Reach End
HTML-код
- Опубликовано: 1 окт 2022
- GfG-Problem Link: bit.ly/3AugzNb
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
The java code by mistakenly is of wrong question, here is the correct one.
class Pair {
int first, second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
class Solution {
int minimumMultiplications(int[] arr,
int start, int end) {
Queue q = new LinkedList();
q.add(new Pair(start, 0));
int[] dist = new int[100000];
for(int i = 0;i
Hey brother can you solve leetcode skiplist problem in Java
Hey Striver ! you have pasted the different Ques's java code there. Please edit it.
Man I guess there's a problem with the inner for loop, instead of going till the 'n' it should go till the arr.length().
I know it works, but it creates confusion. BTW man love your content.♥
@@tejasc7409 no bro this Java code in comment is 100% correct.
@@preetkatiyar969 hey bro I was talking about the java code in the video.... After that the correct java code was pasted here.
@Striver for the time period 12:50, there is a slight error of keeping (12, 1), (30, 1). Steps here was +1, so it will be (12, 2), and (30,2). Same needs to be corrected even in the queue.
And also as there is max limit of 10^5, but you have used 0 to 9999, instead of 99999.
These two were the nitpicks, otherwise the explaination was great, thanks!
thanx for explain these points
Thanks for the clarification, Actually I also got confused...
I came to do same comment😂
the steps are prioritised first so it should be (2,12),(2,30) although (12,2) (30,2) would work for 42 test cases. if not prioritzed it could give error in large area of test cased where the muliplication is actually smaller than the steps.
i came to check same. i also a little bit confused.
Important Note:
If the start value is greater than end value, the answer is still possible because after the mod operation the value will shrink and can reach the end, similarly if at any point, the value is greater than end we cannot discard it as it may lead to the answer at a future point after the mod operation.
Use this test case where arr = {6, 8}, start = 4608, end = 4288, after 12 operations start will reach the end.
For somebody who is not able to make a correct submission on GFG using this code, please make a simple correction that if(start == end) return 0;
Seems a simple mistake but people do miss it.
Thank you Striver. Really appreciate ur efforts! Great content
Correct Striver's Code : class Solution {
public:
int minimumMultiplications(vector& arr, int start, int end) {
// code here
queue q;
q.push({start, 0});
vector dist(100000, 1e9);
dist[start] = 0;
if(start == end) return 0;
while(!q.empty()) {
int node = q.front().first;
int steps = q.front().second;
q.pop();
cout
🙌
Thank you so much bro !!!
thank you so much
ohh yes thanks, dunno how such simple stuff slipped out of my mind
Simple BFS using visited array should also work because we are incrementing at steps of 1. Maintain a counter variable, and return it at the first occurence of the target number (end).
class Solution {
public:
int minimumMultiplications(vector& arr, int start, int end) {
int MOD = 1e5;
queue q;
q.push(start);
int vis[100000] = {0};
vis[start] = 1;
int cntr = 0;
while (!q.empty()) {
cntr++;
int n = q.size();
for (int i = 0; i < n; i++) {
int num = q.front();
q.pop();
if (num == end) return cntr - 1;
for (int j = 0; j < arr.size(); j++) {
int mul = (num * arr[j]) % MOD;
if (!vis[mul]) {
vis[mul] = 1;
q.push(mul);
}
}
}
}
return -1;
}
};
agree
Right...thanks for sharing
had the same thought and implemented it. :D
Had the same thought..Thanks..!!
This should be TLE ig
If someone's thinking here we can improve on space by declaring dist array of size (end + 1) and then we simply don't push the nodes into the queue which are greater then end because nodes greater than end multiplied by any integer can't lead to end. Now, This optimization could have been picked if we don't have to mod the node. Since, we need to mod the value of node, There may be a case where node is greater than end but after mod it becomes such a number say 'num' that 'num' multiplied by any particular array element will make our num value equal to end. Basically greater than end values can again reach to a value that is lesser than end after mod. So, this optimization can't be picked.
Thanks
Thanks A Lot
Thanks a lots. I was also doing same optimization but getting wrong answer.
very helpful. Thanks.
But you can simply make an unordered set to track the visited ones. Coz if you visit the number again then it will always have steps greater than previous so why to use a fixed size array.
Great problem and fantastic explanation!!
One metion that this problem seems more like a bfs problem to me where a visited array would do the job instead of distance array.
i assumed it to be dp problem , beacuse there are many overlapping subproblems
@@pulkitjain5159 yeah me too. the tree he made is recursion tree, isnt it?
Yes but it gave TLE on gfg, when i used bfs with vis array.
@@pulkitjain5159 It 100% looks like DP to me as well.
yes it gives correct answer, But thid ques cant be solved by dp na? because how we will handle the case when when dont reach end?? because one base case can be that when start==end then return 0 , but we can never say that when start>end return -1 due to the mod thing? I saw some comments saying we can use dp but I dont think thats the case here?
After watching every videos in the playlist till now ,I am able to code it by myself..thank you Bhaiya :)
Even finding out the problem is related to graph is very difficult and you said you solved it yourself, how?
There is one test case failing where start==end, just return a statement at the top of the code , if(start==end) return 0;
Thanks
Striver's approach also teaches us various ways to solve a problem and how to apply algorithms in questions
If anyone wants to solve this using without Dijkstra , below is the C++ code
C++ Code using simple BFS and visited array
queue q;
q.push({0,start});
vector visited(100000 , 0);
visited[start] = 1;
while(!q.empty())
{
auto p = q.front();
q.pop();
int steps = p.first;
int node = p.second;
for(auto x:arr)
{
int num = (x*node)%mod;
if(!visited[num]){
visited[num]=1;
if(num == end)return steps+1;
q.push({steps+1,num});
}
}
}
Here Dijkstra is same as BFS as we are always increasing steps by +1 .
@@shashwatanand571 exactly
thanks for your effort, but most likely this would provide a tle...... cause if the end cannot be reached then its not possible for the bfs to end..... please correct me if i am wrong...
I always forget the vis array concept
@@idealspeaker1377 no it won't give, just return a -1 at the end, there will be a time when elements will starting getting repeated in the queue, coz just see
1.) eliminating numbers by not putting them inside the queue if they have already been marked visited
2.) suppose some new numbers are present inside the queue, after certain operations their results will also get repeated, at the end when the queue finishes you return -1;
its so nice to hear about how passionate striver is for the kind of work he does
The previous videos were well explained that I could identify that a PQ is not needed and a queue will suffice.
Great question.
I was curious about how you set questions and test cases? Would love a video maybe on your experience on developing questions like these.
he,s a candidate master so easy for him
Explanation for anyone who thinks this was a problem of DP/Recursion.
Initially I also thight that this was a DP problem, however if we look at the test case :
start = 93
end = 58
a = [87 14 75 23 69 19 88 6 59 92 3 ]
here our start > end already -> so we return -1 however, the question uses mod, therefore sometime in the future 93 might become equal to 58 (in 6 steps).
this way, we cannot come up with a base condition (I wasn't)
also,if we ignore this test case, we our have to memoize our solution using start and current steps, which would get very costly
The recursive solution I wrote in python if you want to have a look (for the Recursive approach ignoring the above mentioned TC) :
def minimumOperations(n: int, start: int, end: int, a: List[int]):
ans = float("inf")
mod = 10**3
if start == end :
return 0
def dfs(start,cur,ans) :
if start > end :
return float("inf")
if start == end :
return cur
for ind in range(n) :
temp = (start * a[ind]) % mod
if temp > start : # if a[ind] == 1, then the recursive approach goes to TLE
ans = min(dfs(temp,cur + 1,ans),ans)
return ans
ans = dfs(start,0,ans)
return ans if ans != float("inf") else -1
Not satisfied with your explanation for why it is not a DP problem , Mod cannot take larger start to a smaller end .. since MOD is fixed in this case.
@@Anonymous_Coder Didi you tried this using recursion and dp? let me know
@@Anonymous_Coder we can't solve it with dfs+memoization etc etc , this problem form a infinite tree after mod value tree will repeat and if you get stuck in some branch which don't have your end ,you will get tle .simple hopes it helps
While I'm solving this problem I have done using following
I notice it only run for 100000 right ? but still I'm not getting proper result it stuck in the loop itself
def minimumMultiplications2(self, arr : List[int], start : int, end : int) -> int:
visit = defaultdict(int)
dp = defaultdict(lambda : float("inf"))
def dp_code(start,end):
if start==end:
return 0
if start>end or start in visit:
return float("inf")
if dp[start]end:
continue
if local in visit:
return dp[local]
result = min(result,dp_code(local,end))
visit[local] = 1
dp[start] = result+1
return dp[start]
if dp_code(start,end)>=float("inf"):
return -1
return dp[start]
understood but it had 2 errors . thanks it was amazing and i am following your series from the beginning
Finally I could do it without even starting the video. Thanks Striver
UNDERSTOOD..........Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Great problem and great explanation. Really helping me with learning these advanced concepts.
Simple bfs with visitied arr and level counting will work.
yess.....but I wonder why striver is teaching dijkstra for this question...🤔🤔
@@SatyamEdits yess same doubt
I am teaching dijsktra because, we are learning problem solving. Once you know the problem solving, you can tweek it. Like in this case, if you see the pattern of solving.
You can easily observe q gives us the smallest distance, so a dist array is not req.
I want you to learn problem solving and not the way I do. If you know dijsktra in deep, you can play around and optimise.
I hope that clears your doubt.
However the complexity stays the same mostly, so I did not cared to change it to visited.
You use visited array he used dist array to eliminate recalculations
Its the power of Dijiksktra works
Striver add one more line in the code, if(start==end) return 0; beacuse it is not passing some of the test cases, And Thanks for teaching these things , really helpful, will suggest my juniors for sure
thanks
thanks guru
I never would have thought of applying graph algorithm in this problem.
same
We can generate all the numbers if the start = 1, end = 9999 and the Array = {1,2,3,4,5,.....9999} but in this case the time complexity will only be O(N) not O(N) * 100000 because in just one traversal you will get to the end.
Thanks.
this code will give wrong answer for start=end (already ) output -1 but should be 0; we have to put an extra condition at the starting of code if(start==end) return 0; without this condition even though it is accepting .
Thanks for the explanation they rectified and without this condition the test case didn't pass
I had a approach where I would divide instead of multiply and using basic Dijkstra max heap to get max divisor and push into heap if it divides and quotient is more than start.
It would fail i presume because of modulo
can we solve this by using DP by pick and notpick statements??
Understood! Super awesome explanation striver
cant it be done using dp like coin change problems
thid ques cant be solved by dp na? because how we will handle the case when when dont reach end?? because one base case can be that when start==end then return 0 , but we can never say that when start>end return -1 due to the mod thing? I saw some comments saying we can use dp but I dont think thats the case here?
I know that it isnt going to be an issue but during the explanation you wrote 9999 instead of 99,999 but it did not affect the code because we define vector with size of 1e5. Great explanation though!
Striver, here's an optimization: we don't really need Pairs at all for this question. We already have the dist[] array to store the current distance of each node, so we can use it to access each node's distance/steps.
Understood! Super awesome explanation as always, thank you very much!!
a little edge case is if start ==end then return 0
Have any one else also thought of doing it with DP? Since we can memoise it in an array similar to what is used here.
yaah
yes
did it work?
Can't this problem be solved via recursion?
it seems dp + recursion + memo can also be used for this
same doubt...looks like kinda knappsnack problem...
it is similar to combination sum where same number can be taken any number of times.Have you done using this method?
we can't use since the constraints are high
Thank you for the video. The problem is during interview, there is no white board because it's virtual and they only want me to use code editor. I am a visual person and not able to draw really makes it more difficult for me.
True same for me
Hi Striver, It's hard to judge that this question will be solved using graph. What will be the intuition that the concept used is Dijkstra Algorithm because at the first glance it appears to me of a DP ques?
Usually shortest distance and these kind of questions with restricted number of nodes, can be solved using the standard bfs or djikstra
What would be the base case in dp
Dp cannot be applied in the same complexity, because we are path dependent here. Like we care about what nunbers we visited in the past, and not just the minimum count.
Like assume you arrived at x at 5 steps, and to arrive at x you took 5 different numbers.
Next time you arrive at x, you might arrive via different path, so you cannot be just dependent on the min count. Hence DP will be costly as you have to memoize the path with the steps at any given node when you reach
@@takeUforward samaj nahi aaya bhayiya achhe se ki dp kyon nahi use kar rahe
@@krishanpratap3286 try writing recurrence of DP, and you will see you can visit some point from multiple paths, so memoization does not works, hwoever recursion will give you correct answer.
Understood!!
Hi striver why don't you use the distance array size as end distance and when multiplication of the element reaches more than end distance you can continue with next element so that will be reduce you space complexity am i correct ?
Yes you can, I wanted to give you the logic, rest a visited array will also work fine..
When i take the distance array size as end and add the condition when (num>end) then continue ,but it is giving wa. can you check.
class Solution {
private:
int MOD = 100000;
int findMinSteps(vector& arr, int start, int end){
queueq;
vectordist(end,INT_MAX);
dist[start] = 0;
q.push({0,start});
while(!q.empty()){
int number = q.front().second;
int steps = q.front().first;
q.pop();
for(auto &a:arr){
int num = (number * a)%MOD;
if(num>end)continue;
else if(num==end)return steps+1;
else if(dist[num]>steps+1){
dist[num] = steps+1;
q.push({steps+1,num});
}
}
}
return -1;
}
public:
int minimumMultiplications(vector& arr, int start, int end) {
// code here
int minSteps = findMinSteps(arr,start,end);
return minSteps;
}
};
@@aakashgoswami2356 yes it is giving wrong answer,have you got the reason?
@@rishabhgupta9846 not yet bro.
@@rishabhgupta9846 Refer to my comment on his mistake...
Time Complexity : We can get at max 100000 nodes and the answer will lie within these 100000 nodes(the repeated results in the same level and prime numbers are not being considered).
so, Time complexity : O(100000)
No need to use Djisktra Algo :
BFS Approach :
int minimumMultiplications(vector& arr, int start, int end) {
// code here
int mo = 100000;
queueq;
q.push({0, start});
int n = arr.size();
vectorvisted(mo);
visted[start] = 1;
while (!q.empty())
{
int node = q.front().second;
int steps = q.front().first;
q.pop();
if (node == end)
return steps;
for (int i = 0; i < n; i++)
{
int x = (arr[i] * node) % mo;
if (visted[x])
continue;
visted[x] = 1;
q.push({steps + 1, x});
}
}
return -1;
}
if we dont use a visited array will it give tle?
@@gagankainthola8454 yes
I think we can do it with a simple BFS as well.
The complexity of djiktra is n^2log(n) but we need a nlogn solution according to given constraints
don't you think it's a question of dp ?, we dekha jaaye toh bfs ek kind ka dp hi hai
How to identify if it is not a recursion/dp problem but a graph problem.
I actually had a confusion choosing between dynamic programming and graphs , for this particular question .
I am not sure about it, but i think we have to make n*n dp which will result in tle , while using dijsktra we can solve this in (V+E)logV
Thank you sir 🙏
Already done 5 days ago on GFG POTD🔥
Impeccable explanation!
Thank you very much. You are a genius.
Nicely Explanied
Can anyone help me understand one doubt
Like in some problems we check whether that if we reached the destination while pushing into queue and if we reached we return it and in some we check this while poping out
Does this is completely depends on the question or is there something i am missing???
So this depend on whether we are working with weighted graph or Unweighted/unit weight graph , in case on unwighted graph if you observe at the value of distance will increase linearly so first we make call for distance 1 then distance 2 and so on....so in this case when you reach the ans you can be sure that this is the min distance so you can return at the time of Insertion only . BUT consider the case then the it is weighted graph then you might reach the answer with min STEPS but not necessary with with min COST . so we not sure if we have a reached the optimal solution , and also we use PRIORITY QUEUE in this case for the same reason , when we pop the element and get the answer you can be sure since PRIORITY QUEUE will put the MIN cost at top . I think this is because of the fact that Dijkstra tries to go for min path each time so it goes for local minima which cause this issue .
using a priority queue with the number of steps as a key also works will that help with the TC to some extent?
It works but increases the time complexity, by logarithmic factor. why use the PQ when you are increasing steps value by +1. Queue works fine
The code for this problem is not passing all the test cases there is some issue with the code..I have also checked the TUF site the code is not passing all the test cases ..Please have a look
understood sir ,thankyou for your effort
understood striver easy explanation
The time complexity is certainly O(1e5 * n)... Just write 1 to 10000 as the array and unless gfg has a supercomputer it will give TLE
had the same doubt,why is it working?
maybe aise test case nahi diye honge @@OmSingh-ze1rn
@@user-qq5bb7bh5zquestion statement clear nahi hai na. Honi chahiye.
I am keeping track of visited numbers instead of steps and it works.
class Solution {
public:
int minimumMultiplications(vector& arr, int start, int end) {
using vi = vector;
queue q;
vector visited(1e5+1, false);
set nums;
for(int num: arr) {
nums.insert(num);
}
visited[start] = true;
q.push({0, start}); // steps, product
while(q.size()) {
auto node = q.front(); q.pop();
int steps = node[0], product = node[1];
for(int num: nums) {
int newProduct = (1LL*product*num)%100000;
if(visited[newProduct]) continue;
visited[newProduct] = true;
if(newProduct == end) return 1+steps;
else q.push({1+steps, newProduct});
}
}
return -1;
}
};
i solved this problem as gfg potd
Understood Sir, Thank you very much
ig you don't need dijkstra's (maintaining dist array). since all edges are 1. it's just bfs.
agree, this seems to be pain BFS
Understood
beautiful problem🙌🙌
it can also be done with the recursion
is this problem solvable without using dist vector we directly check from queue if nuymber == end return steps ??
10000 mod 100000 won't be 0, right?
100000 mod 100000 will be 0.
Slight error in writing it down, you can either edit it as mod 10000 and make the current thing work, or make the size from 9999 to 99999.
Thank you for your efforts, avid follower.
correct
Can't we do this by simple bfs traversal, what is the need of the dist array in this question
In q is it store at 1,30 or 2,30 ?
Because previously it is coming from 1,6 now 6 is multiplied by 5
So previously step is 1 now 1+1 =2
Solved without watching video, thanks a ton for this series 💯💯
why is the condition num == end inside the for loop , generally in other questions it is after pop
you can also write after pop but condition will be if(node==end) return steps;
can't we do it using BFS levels directly?
Yes we can
understood clearly.
How to identify this is not a DP problem? Because my initial thought was to check all possible states like in DP problem.
This ques cant be solved by dp because how we will handle the case when when don't reach end?? because one base case can be that when start==end then return 0 , but we can never say that when start>end return -1 due to the mod thing? I saw some comments saying we can use dp but I dont think thats the case here?
@@user-qq5bb7bh5z
We can try to solve it with dp but it will cause TLE for very large value.
class Solution {
int mod = 100000;
int memo(int[] arr, int start, int end, int steps, int dp[]) {
if(start == end) return steps;
if(start > end) return Integer.MAX_VALUE-1000;
if(dp[start]!=-1) return dp[start];
int minSteps = Integer.MAX_VALUE;
for(int val : arr){
minSteps = Math.min(memo(arr, (start*val)%mod, end, steps+1, dp), minSteps);
}
dp[start] = minSteps;
return minSteps;
}
int minimumMultiplications(int[] arr, int start, int end) {
int dp[] = new int[end+1];
Arrays.fill(dp, -1);
int steps = memo(arr, start, end, 0, dp);
return steps== Integer.MAX_VALUE-1000? -1 : steps;
}
}
@@user-qq5bb7bh5z Ok at worst case I would go tell 10pow5 depth (but maybe more comparisions). But if I encountered a value that is already visited then I would simply return.
This is basically BFS but with recursion.
If someone who knows DP comes across this question, the first thought in their head would be to use DP, its hard to digest that this problem turned out to be on graph.
Also let me tell you that DP(memoization) won't work here because it will end up in TLE.
why tle if we memoize then only 100000 cases will exist only ? can you please share your tle dp code
@@ROHITKUMAR-xp2xe The only way you can solve this question is by using a BFS approach, but the memorization follows DFS approach which will lead to TLE.
@@harshithvh8194 can you please share me your tle dp code ?? I have written dp code but it is giving rte everytime
Hello everyone. For anyone getting TLE -> If you using log(n) time for visited marking instead of a linear vector, the time constraints are such that it will TLE so just use linear structures
When we reach the end node for the first time, won't it always be minimum steps to reach the end node?
(using BFS/Dijkstra Algo, since all the edges are at the distance/step of 1)
yes
Any reason why we are storing the steps/distance in queue..when it is already there in the distances array?
why it is giving TLE if done using simple BFS and visited array
understood
Hi striver can this be done by backtracking also
A summarized version of the Java Code:
class Pair{
int steps; int product;
public Pair(int steps, int product){
this.steps = steps; this.product = product;
}
}
class Solution {
int minimumMultiplications(int[] arr, int start, int end) {
Queue q = new LinkedList();
int[] dist = new int[100000];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[start] = 0;
q.offer(new Pair(0,start));
while(!q.isEmpty()){
int s = q.peek().steps;
int p = q.peek().product;
q.poll();
if(p == end) return s;
for(int factor : arr){
int newStart = (p * factor)%100000;
if(s+1 < dist[newStart]){
dist[newStart] = s+1;
q.offer(new Pair(s+1, newStart));
}
}
}
return -1;
}
}
I have confusion here, with Striver's code. While doing the dry run he showed the pair order in the queue as (steps, node). But while coding he wrote (node, steps). But the dry run order should be the correct one in my opinion.
it would not matter
Thank you bhaiya
why do u need dist array when u are already storing steps in queue...? can't understand
why cant we do it using recursion,
int solve(int start, int end, vector &arr){
//base case
if(start > end)return 1e9;
if(start == end)return 0;
int count = 1e9;
for(int i=0; i
Understood 🙏Thank you❤️🫰🏻
Can we not skip the array numbers, that are not divisible by end ? If it is not divisible by end, it will create unnecesarry products that we need to check.
we can also use plain vanilla BFS at level by level with a visited set.
def minimumMultiplications(self, arr : List[int], start : int, end : int) -> int:
# code here
if start == end:
return 0
queue = deque()
seen_nums = set()
seen_nums.add(start)
queue.append(start)
curr_steps = 0
min_val = start
while queue:
curr_steps += 1
qLen = len(queue)
for _ in range(qLen):
num = queue.popleft()
for elt in arr:
new_num = (num * elt) % 100000
if new_num == end:
return curr_steps
if new_num not in seen_nums:
seen_nums.add(new_num)
queue.append(new_num)
return -1
Understood 👍
why didn't we push (0, start) in the queue?
awesome!!! understood
Striver bhaiya, ye question aapke kisi coding round me aaya tha na,sach sach batayega😉🤫
for those who attempted this q on their own with same logic by using set to track vis , and getting tle Remove that set
Sir, had u simply counted the number of levels using simple queue, that would also suffice.. saving space and time. The moment you spot some duplicacy skip that element.
In the explanation he took queue as (steps,node) but in solution he took node,steps.
guys we can't solve it with dfs+memoization etc etc , this problem form a infinite tree after mod value tree will repeat and if you get stuck in some branch which don't have your end ,you will get tle .simple hopes it helps
Do we need to store steps in dist array. Cant we directly put it in queue as it is storing in increasing order only, and we will return step whenever end is reached ???
17:10 I wrote the exact code on my own but I did not put the check at line no. 29 and got TLE.
This problem can be solved by Backtracking ( can call it DFS since it is using recursion ) , BFS with queue , BFS with priority_queue (Dijkstra).....please do correct me if I am wrong
how will you solve it with dfs it will give the its infinite tree problem mate, tree its self repeat if u traversing a branch you can't go out as dFs we are using
you can solve it with bfs what ever data structure you want to use BFS will give you result;
understood ❤
Dijkstra makes more sense with weighted graphs here simple bfs would suffice
Why don't we use a map instead of a vector to store the distance/steps, in this way, we can save up space
Somewhat like this -:
nt minimumMultiplications(vector& arr, int start, int end){
if(start == end) return 0;
unordered_map mpp;
queue q;
q.push({0, start});
while(!q.empty()){
int steps = q.front().first;
int node = q.front().second;
q.pop();
for(int it : arr){
int curr = (it * node) % 100000;
if(curr == end) return steps + 1;
if(mpp.find(curr) == mpp.end()){
mpp[curr] = steps + 1;
q.push({mpp[curr], curr});
}else if(mpp[curr] > steps + 1){
mpp[curr] = steps + 1;
q.push({mpp[curr], curr});
}
}
}
return -1;
}
this can also be done using bfs