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
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.♥
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.
@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!
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.
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; } };
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
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.
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.
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
@@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:
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.
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?
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}); } } }
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...
@@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;
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.
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; }
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.
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
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.
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)
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.
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.
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
Question is not explained well. Nowhere it is mentioned that we can multiply any number of times. Even time complexity is written as 10^5. This doesn't clarify the complexity
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
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 .
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 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!
If someone got thaught of doing it with DP approach.Let me tell you that we can't becuase here it is possible that end is unreachable and DP never works in the problems where goal is unrecahable.
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)
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?
Simple java code for gfg : class Solution { int minimumMultiplications(int[] arr, int start, int end) { int n = arr.length; int MOD = 100000; Queueq = new LinkedList(); q.add(new int[]{0,start}); boolean[] vis = new boolean[100000]; Arrays.fill(vis,false); vis[start] = true; while(!q.isEmpty()){ int[] node = q.poll(); int curr_number = node[1]; int curr_oper = node[0]; if(curr_number == end)return curr_oper; for(int i=0;i
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.
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.
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.
just bfs would probably be better and more intuitive for this problem as multiplications will always be increasing by 1 and as soon as end is reached, we will return the number of multiplications so far or eventually -1 if end is never reached
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?
@@AnushkaGupta-x6w 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; } }
@@AnushkaGupta-x6w 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.
UPDATED JAVA CODE: class Solution { class Pair { int node; int distance; public Pair(int node, int distance) { this.node = node; this.distance = distance; } } int minimumMultiplications(int[] arr, int start, int end) { // Early return if start is already equal to end if (start == end) return 0; int[] dist = new int[100000]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] = 0; Queue q = new LinkedList(); q.add(new Pair(start, 0)); while (!q.isEmpty()) { Pair curr = q.remove(); int currNode = curr.node; int currDist = curr.distance; for (int num : arr) { int n = (currNode * num) % 100000; // If `end` is reached, return the current distance + 1 if (n == end) return currDist + 1; // Update distance if a shorter path is found if (currDist + 1 < dist[n]) { dist[n] = currDist + 1; q.add(new Pair(n, currDist + 1)); } } } // If end node is unreachable, return -1 return -1; } }
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.
@@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.
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
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;
Why cant we use DP? my initial though was it is a dp problem....if i would have got this in an interview i would have gone for DP and maybe messed up. how do we get the intution and differentiate problems like this which seems like DP but they aare a graph problem
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 ?
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; } };
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?
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
@@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.
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.
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.
@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.
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
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
or you can move that if condition right after popping, that way you do not need a duplicate if
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.
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]
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?
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
Finally I could do it without even starting the video. Thanks Striver
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
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?
understood but it had 2 errors . thanks it was amazing and i am following your series from the beginning
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
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
UNDERSTOOD..........Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
Great problem and great explanation. Really helping me with learning these advanced concepts.
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.
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;
}
};
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)
Understood! Super awesome explanation striver
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.
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
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
Question is not explained well. Nowhere it is mentioned that we can multiply any number of times. Even time complexity is written as 10^5. This doesn't clarify the complexity
i am not able to find that it is bfs problem . i will try to solve it using dp if i not know that i was solving graph series
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
test case : if (start == end)return 0;
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
Already done 5 days ago on GFG POTD🔥
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
@@AnushkaGupta-x6wquestion statement clear nahi hai na. Honi chahiye.
Understood bhaiya..
a little edge case is if start ==end then return 0
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;
}
}
4
9 12 18 19
5 5
I think they updated the test cases. Expected output is 0 for this input. But for your code returns -1
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!
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
I think we can do it with a simple BFS as well.
it can also be done with the recursion
The complexity of djiktra is n^2log(n) but we need a nlogn solution according to given constraints
Understood! Super awesome explanation as always, thank you very much!!
Nicely Explanied
understood striver easy explanation
Solved without watching video, thanks a ton for this series 💯💯
If someone got thaught of doing it with DP approach.Let me tell you that we can't becuase here it is possible that end is unreachable and DP never works in the problems where goal is unrecahable.
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
Impeccable explanation!
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?
How to identify if it is not a recursion/dp problem but a graph problem.
Understood Sir, Thank you very much
Simple java code for gfg :
class Solution {
int minimumMultiplications(int[] arr, int start, int end) {
int n = arr.length;
int MOD = 100000;
Queueq = new LinkedList();
q.add(new int[]{0,start});
boolean[] vis = new boolean[100000];
Arrays.fill(vis,false);
vis[start] = true;
while(!q.isEmpty()){
int[] node = q.poll();
int curr_number = node[1];
int curr_oper = node[0];
if(curr_number == end)return curr_oper;
for(int i=0;i
While coding you used node,step but in explanation you used step,node
It doesn't matter coz we ain't using priority queue.
Thank you very much. You are a genius.
Striver bhaiya, ye question aapke kisi coding round me aaya tha na,sach sach batayega😉🤫
We can improve complexity by taking case tha multiplication shouldn't go beyond target
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.
beautiful problem🙌🙌
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
understood sir ,thankyou for your effort
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 sir 🙏
i solved this problem as gfg potd
Code I wrote:
const int MOD = 1e5;
class Solution {
public:
int minimumMultiplications(vector& arr, int start, int end) {
// code here
if(start == end) return 0;
queue q;
q.push({0, start});
vector steps(MOD, INT_MAX);
while(!q.empty()){
auto pai = q.front();
q.pop();
int num = pai.second, stepCount = pai.first;
for(int i=0;i stepCount + 1){
steps[num] = stepCount + 1;
q.push({stepCount+1, num});
}
num = org;
}
}
if(steps[end] == INT_MAX)
return -1;
return steps[end];
}
};
don't you think it's a question of dp ?, we dekha jaaye toh bfs ek kind ka dp hi hai
Thank you bhaiya
just bfs would probably be better and more intuitive for this problem as multiplications will always be increasing by 1 and as soon as end is reached, we will return the number of multiplications so far or eventually -1 if end is never reached
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?
@@AnushkaGupta-x6w
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;
}
}
@@AnushkaGupta-x6w 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.
UPDATED JAVA CODE:
class Solution {
class Pair {
int node;
int distance;
public Pair(int node, int distance) {
this.node = node;
this.distance = distance;
}
}
int minimumMultiplications(int[] arr, int start, int end) {
// Early return if start is already equal to end
if (start == end) return 0;
int[] dist = new int[100000];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
Queue q = new LinkedList();
q.add(new Pair(start, 0));
while (!q.isEmpty()) {
Pair curr = q.remove();
int currNode = curr.node;
int currDist = curr.distance;
for (int num : arr) {
int n = (currNode * num) % 100000;
// If `end` is reached, return the current distance + 1
if (n == end) return currDist + 1;
// Update distance if a shorter path is found
if (currDist + 1 < dist[n]) {
dist[n] = currDist + 1;
q.add(new Pair(n, currDist + 1));
}
}
}
// If end node is unreachable, return -1
return -1;
}
}
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
A little off topic but is there a way to do this using traditional DP method since there are repeating sub problems?
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
We wouldnt know when to stop the recursion
this can also be done using bfs
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
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
instead of pair in queue we can also find answer on the basis of their level
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
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;
can we solve this by using DP by pick and notpick statements??
Let me tell you that we can't becuase here it is possible that end is unreachable and DP never works in the problems where goal is unrecahable.
Dijkstra makes more sense with weighted graphs here simple bfs would suffice
Why cant we use DP? my initial though was it is a dp problem....if i would have got this in an interview i would have gone for DP and maybe messed up. how do we get the intution and differentiate problems like this which seems like DP but they aare a graph problem
Java code:
class Pair{
int noperation;
int muln;
Pair(int noperation,int muln){
this.noperation = noperation;
this.muln = muln;
}
}
class Solution {
int minimumMultiplications(int[] arr, int start, int end) {
int mod = (int)(1e5);
int dist[] = new int[mod+1];
Arrays.fill(dist,(int)1e9);
dist[start] = 0;
Queue q = new LinkedList();
q.add(new Pair(0,start));
while(!q.isEmpty()){
Pair curr = q.poll();
int onoperation = curr.noperation;
int omuln = curr.muln;
if(omuln==end) return dist[omuln];
for(int i =0;i(onoperation+1)){
dist[newmuln] = onoperation+1;
q.add(new Pair(dist[newmuln],newmuln));
}
}
}
return -1;
}
}
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...
why didn't we push (0, start) in the queue?
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 clearly.
Understood 🙏Thank you❤️🫰🏻
can't we do it using BFS levels directly?
Yes we can
it can be done using bfs, just sort arr :)
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
Let me tell you that we can't use DP becuase here it is possible that end is unreachable and DP never works in the problems where goal is unrecahable.
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 we solve this using simple recursion using pick /not pick approach?
Never.What you will put base case to stop your recursion as it is possible that you will never reach to end
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;
17:10 I wrote the exact code on my own but I did not put the check at line no. 29 and got TLE.
Any reason why we are storing the steps/distance in queue..when it is already there in the distances array?