What I think the idea/ need of using GCD in this algorithm is that it helps combining 2 cases into single case. Think of this algo without GCD, then we have 2 scenarios, 1- When both n and k are multiples of each other , in this case we know that we will form n/k number of cycles/set and then move elements in those cycle iteratively (using j+d % n and when d == i then we will increment our outer loop) in this way we will go for each cycle. 2- When n and k are not multiples also think in a way that you want k(th) element on first position and likewise the succeeding elements so we will use the same approach (d+j % n till d == 0) in this case we will encounter d == 0 only one time and hence we know that will be the end of algorithms because before d will end up being 0 it will cover all the possible values. So now if we see that these 2 conditions 1- when outer loop runs n/k times and 2- when outer loop will run only 1 time. this can be achieved or calculated using gcd(n,k). So either increase your lines of code making 2 handling 2 different scenarios then you will be clear or if you understand this then apply GCD and make your code short.
Thabnks bro. I had same assumption but could not find resource to become clear. But you explained very well. In the above video he should have given the appropriate reason.
Till now i did not come across such a simple explanation..... Good job Good animation I watched 3 different tutorials but here I understood. Thanks....
Seriously this is the best video I have seen till now, the way you have explained it was awesome. Thanks a lot for writing the blog as well. This is a pure gem teaching style 💯
Nice work there, but modulo is effectively implemented by division, so with modern branch prediction and condition k=n) d-=n; But juggling algorithm probably behaves bad on caches anyway as addresses spread over the whole array range; at least for large k this could be a problem.
Hi. I am a new comer to programming. I read your comment and it intrigues me. But I am not able to fully understand it. Can you explain what you where trying to say with branch prediction and caches issue. It seems interesting.
@@whimsicalkins5585 CPUs loose a lot of time when they need to jump between different lines of code, that's why branch prediction was implemented, so modern CPUs predict where the next commands to execute are and prefetches them. CPU uses Cache for those prefetches, and Cache is expensive and limited, therefore jumping a lot around in the code over large areas leads to cache misses and therefore time where the CPU has to wait for Code or Data to be loaded into the Cache, and those waiting times of course slow the code.
@@QuantenMagier Understood. But how does ditching the modulo and using if(d>=n) d-=n makes the code more efficient than before? And when you say "addresses spread over the whole array" do you mean that "j" and "k" could possibly be anywhere far apart inside the array and this spatial difference is so huge when k >> j which causes possible cache miss ?
@@whimsicalkins5585 Yes the modulo operation is also slow as it needs dedicated hardware for the division and division takes 25+ CPU cycles compared to my proposed addition and substraction which only take one CPU cycle each. The only problem is the "if" which is a compare-and-jump instruction, but as long as the CPU jump prediction is correct (which should be the case here most of the time) that also only takes 2-3 cycles. So my code takes 5 cycles per normal execution compared to the 25 cycles for the modulo operation. A cache miss/jump prediction error would probably be about 100 cycles penalty but after 4-5 executions of the loop my code already saves over 100 cycles and therefore more than makes up for the misses. And you are right about the cache misses for huge k, because if the addresses are to far apart and unpredictable they don't fit into the cache anymore.
void rotate_array(int arr[], int d, int n) { /* To handle if d >= n */ d = d % n; for (int i = 0; i < gcd(d, n); i++) { /* move i-th values of blocks */ int temp = arr[i]; int j = i; while (1) { int k = j + d; if (k >= n) k = k - n; if (k == i) break; arr[j] = arr[k]; j = k; } arr[j] = temp; } } The code in this video is bad
Bro if gcd is 1 then still this logic will work... because when j reaches to last index then next time j will be equal to second index.. this will continue and the array would be rotated. Suppose n is 5 and k is 2...so gcd is 1 when j becomes 4 i. e. last index next time it will become i. e. second index and will continue like this.... Sorry if u r unable to understand my thoughts then please dry run the code and you will find that this logic works for gcd = 1
Don't know about internet but better than GeeksForGeeks for sure. Much helpful after one is getting confused at some point and struggling to get head straight to the explanation on Geeks for Geeks article. There should be a video to every problem. And let that video be based on Most likes from youtube or any other channel.
# rotate array by k elements def rot(arr, k): if len(arr) < k: print("error") else: for i in range(k): x = arr[0] arr.append(x) arr.pop(0) print(arr) rot([1,2,3,4,5,6],3)
The explanation is too good and it's easy to understand. Thanks for the video. but I've one doubt, Is it possible to use the juggling algorithm to rotate the array to the *right* (not to the left)?
This video explains how algo is working pretty well and how the elements are being shifted cyclically. But the biggest question is why gcd is taken? Can someone explain this? Why we are running first loop gcd times?
explain ar=[1,2,3,4,5,6,7] where d is not becoming equal to i in array size that is in A[j] j becomes greater than 7 0 0 (0+2)%7=2 0 2 (2+2)%7=4 0 4 (4+2)%7=6 0 6 (6+2)%7=1 0 8 (8+2)%7=3 till now also d is not becoming equal to i so this is not going to happen ?
for gcd = 1 the for loop will be for(i =0; i < 1; i++) //i < gcd(7,2) i.e. i < 1 { j = i // here j will get a value 0 since i is 0 in first and only pass temp = a[j] // temp = a[0] while (1) { d = (j + k )%n //k =2 therefore d will be 2 i guess you followed me till here... now i will give you the iterations here on let the array be [1,2,3,4,5,6,7] iteration 1: d = 2, j = 0 a[j] = a[d] a = 3,2,3,4,5,6,7 temp = 1, j = 2 iteration 2: d = 4, j = 2 a[j] = a[d] a = 3,2,5,4,5,6,7 temp = 1, j = 4 iteration 3: d = 6, j = 4 a[j] = a[d] a = 3,2,5,4,7,6,7 temp = 1, j = 6 iteration 4: d = 8%7 = 1 , j = 6 a[j] = a[d] a = 3,2,5,4,7,6,2 temp = 1, j = 1 iteration 5: d = 3, j = 1 a[j] = a[d] a = 3,4,5,4,7,6,2 temp = 1, j = 3 iteration 6: d = 5, j = 3 a[j] = a[d] a = 3,4,5,6,7,6,7 temp = 1, j = 5 now d =7%7 = 0 //hence d == i is true and the while loop breaks and a[j] = temp that is a[5] = 1 hence the array becomes 3,4,5,6,7,1,2 So the above code works just fine... hope you got it
No it is not a limitation. I will give you an example here. Say we want to left shift 1 2 3 4 5 6 7 (with n = 7 and k = 2) Since GCD is 1, yes there will be only one iteration. But in that 1 iteration, complete array would be done. i = 0, temp = 1 j = 0, d = 2 --> a[0] = a[2] --> 3 2 3 4 5 6 7 j = 2, d = 4 --> a[2] = a[4] --> 3 2 5 4 5 6 7 j = 4, d = 6 --> a[4] = a[6] --> 3 2 5 4 7 6 7 j = 6, d = 1 (= (j + k) % n = (6 + 2) % 7) --> a[6] = a[1] --> 3 2 5 4 7 6 2 j = 1, d = 3 --> a[1] = a[3] --> 3 4 5 4 7 6 2 j = 3, d = 5 --> a[3] = a[5] --> 3 4 5 6 7 6 2 j = 5, d = 0 --> a[5] = temp because d == i --> 3 4 5 6 7 1 2 So, when j = 6, that computation of the d using modulus makes the algorithm to cycle around the array within the same set i
When I submitted this solution in Leetcode(189), for the input-[1,2,3] when k=4, the accepted output in leetcode is [3,1,2] but the output from this code is [2,3,1]. The above solution needs one more condition to make it complete- if(k>n) k-=n
That will run fine Gcd is 1 means K=1 Then no of set is 1 Okay then lets move to inner while loop (when i=0) j=i=0 Then d=(j+k)%n => d=(0+1)%n=0 Then inside while loop If d is equal to i then break the loop Here d==0==i Then inner while loop will stop Then a(j)=temp
please make a video on maths behind it...read first explanation of this link and explain it...i'm not able to get it.. link is stackoverflow.com/questions/23321216/rotating-an-array-using-juggling-algorithm
Source Code : www.codewhoop.com/array/rotation-in-place.html
Support Us: www.patreon.com/codewhoop
This is the best explanation of array rotation using Juggling Algorithm out there. It is better than the video by GeeksForGeeks. Thank you.
Agreed :-)
i also come from geekforgeek
Geeks for geeks didn't explain the logic behind this method at all
Exactly. Thank you so so much!
Thank
Best explanation of juggling algorithm I've ever seen.
bro, I just subscribed watching only this video of yours!
Hats off to your explanations!
don't stop making videos!
Best explanation of juggling algorithm I've ever seen. And by the way it is way better than the video by GeeksForGeeks. Thank you.
Yeah. I think u mug up code very well. please describe the reason of using GCD.
What I think the idea/ need of using GCD in this algorithm is that it helps combining 2 cases into single case.
Think of this algo without GCD, then we have 2 scenarios, 1- When both n and k are multiples of each other , in this case we know that we will form n/k number of cycles/set and then move elements in those cycle iteratively (using j+d % n and when d == i then we will increment our outer loop) in this way we will go for each cycle.
2- When n and k are not multiples also think in a way that you want k(th) element on first position and likewise the succeeding elements so we will use the same approach (d+j % n till d == 0) in this case we will encounter d == 0 only one time and hence we know that will be the end of algorithms because before d will end up being 0 it will cover all the possible values.
So now if we see that these 2 conditions 1- when outer loop runs n/k times and 2- when outer loop will run only 1 time. this can be achieved or calculated using gcd(n,k).
So either increase your lines of code making 2 handling 2 different scenarios then you will be clear or if you understand this then apply GCD and make your code short.
Thabnks bro. I had same assumption but could not find resource to become clear. But you explained very well. In the above video he should have given the appropriate reason.
Best Explanation of this Problem I found on the Internet.Thanks.
You're Welcome !
Till now i did not come across such a simple explanation.....
Good job
Good animation
I watched 3 different tutorials but here I understood.
Thanks....
Seriously this is the best video I have seen till now, the way you have explained it was awesome. Thanks a lot for writing the blog as well.
This is a pure gem teaching style 💯
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
better than any arrays rotation videos available so far i understood it so damn well thnx :)
The best explanation for juggling algo !!!!
Wow...so much clear cut explanation...thanks
Only video! which explains juggling algo very well.👍
Thanks for the concise explanation! Cheers!
very very good explanation.......... it is best explanation ever
Thanks dude, and explanation is so good🔥
Your explanation is precise, quick and straight to the point.
Best explanation of juggling algorithm.. Thank you.. ♥️♥️♥️
Nice work there, but modulo is effectively implemented by division, so with modern branch prediction and condition k=n) d-=n;
But juggling algorithm probably behaves bad on caches anyway as addresses spread over the whole array range; at least for large k this could be a problem.
Hi. I am a new comer to programming. I read your comment and it intrigues me. But I am not able to fully understand it. Can you explain what you where trying to say with branch prediction and caches issue. It seems interesting.
@@whimsicalkins5585 CPUs loose a lot of time when they need to jump between different lines of code, that's why branch prediction was implemented, so modern CPUs predict where the next commands to execute are and prefetches them. CPU uses Cache for those prefetches, and Cache is expensive and limited, therefore jumping a lot around in the code over large areas leads to cache misses and therefore time where the CPU has to wait for Code or Data to be loaded into the Cache, and those waiting times of course slow the code.
@@QuantenMagier Understood. But how does ditching the modulo and using if(d>=n) d-=n makes the code more efficient than before? And when you say "addresses spread over the whole array" do you mean that "j" and "k" could possibly be anywhere far apart inside the array and this spatial difference is so huge when k >> j which causes possible cache miss ?
@@whimsicalkins5585 Yes the modulo operation is also slow as it needs dedicated hardware for the division and division takes 25+ CPU cycles compared to my proposed addition and substraction which only take one CPU cycle each. The only problem is the "if" which is a compare-and-jump instruction, but as long as the CPU jump prediction is correct (which should be the case here most of the time) that also only takes 2-3 cycles. So my code takes 5 cycles per normal execution compared to the 25 cycles for the modulo operation. A cache miss/jump prediction error would probably be about 100 cycles penalty but after 4-5 executions of the loop my code already saves over 100 cycles and therefore more than makes up for the misses.
And you are right about the cache misses for huge k, because if the addresses are to far apart and unpredictable they don't fit into the cache anymore.
@@QuantenMagier Thank You.
Thanks for the explanation with the help of a beautiful insight.❤
Best explaination , was struggling to understand this,Thanks
clean simple and best explanation!
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
OMG sir you hit that topics so clearly, big thanks for you, help me a lot
Bro but what if the gcd is 1 , i.e if n = 7 , d = 5 , gcd is one right , can somebody help me , how to overcome this problem ?
void rotate_array(int arr[], int d, int n)
{
/* To handle if d >= n */
d = d % n;
for (int i = 0; i < gcd(d, n); i++)
{
/* move i-th values of blocks */
int temp = arr[i];
int j = i;
while (1)
{
int k = j + d;
if (k >= n)
k = k - n;
if (k == i)
break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
The code in this video is bad
Yes i am having the same issue like n=9 and d=2 so gcd must one here how we are going to do that then
Bro if gcd is 1 then still this logic will work... because when j reaches to last index then next time j will be equal to second index.. this will continue and the array would be rotated.
Suppose n is 5 and k is 2...so gcd is 1
when j becomes 4 i. e. last index next time it will become i. e. second index and will continue like this....
Sorry if u r unable to understand my thoughts then please dry run the code and you will find that this logic works for gcd = 1
Great Explanation 👌👌
Fabulous Explanation
Thanks for the explanation. Great job!
What's the intuition behind the gcd part?
Great Explaination bro... unlimited likes
Thanks a lot for this video. It was really difficult for me to understand before but after watching your video, I completely understood it.
Very good explanation.....
Don't know about internet but better than GeeksForGeeks for sure. Much helpful after one is getting confused at some point and struggling to get head straight to the explanation on Geeks for Geeks article. There should be a video to every problem. And let that video be based on Most likes from youtube or any other channel.
oh man you just rock it .Thanks alot
Just a side note: The implementation you show at around 14:30 is plain ANSI-C, and nothing that needs C++.
Awesome explanation... Kudos to you....
This is the best explanation.Much better than gfg. Thank you so much 🥰🥰😊😊
I need to watch it one more time to understand it well
Can someone please tell me why we calculate the GCD of n and k for finding sets ??? Please explain
# rotate array by k elements
def rot(arr, k):
if len(arr) < k:
print("error")
else:
for i in range(k):
x = arr[0]
arr.append(x)
arr.pop(0)
print(arr)
rot([1,2,3,4,5,6],3)
If arry=[1,2,3,4,5]; and we need to rotate it 2 times then value of d=6 so what to do. Can you please explain me.
Very nicely explained . . . Thanks
Good explanation! Thanks.
best explanation of tis algorithm. very thank u
You're Welcome :)
please also upload Block swap algorithm for array rotation
The explanation is too good and it's easy to understand. Thanks for the video.
but I've one doubt,
Is it possible to use the juggling algorithm to rotate the array to the *right* (not to the left)?
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
Really i'm so surprise.Because this is the best tutorial.Thank you very much.
You are welcome!
Can you explain what happens when the GCD between two numbers is 1.
It will still work but the time complexity becomes O(n^2), basically rotating it one by one
@@snake3276120 so for n being a prime number, rotations is the fastest way
Awesome Please upload more videos based on tree and dynamic programming
Thanks, will surely do in future !!
how to use this algo for right rotation?
ADITYA KUMAR n - left rotation where n is size
Nice explanation good work ...
you are a legend
Very nice 👌
good explaination
A nice video and a sweet voice, thank you.
thanks bhai...samaj me aa gaya
What we will do if right rotation is asked?
Very helpful
This video explains how algo is working pretty well and how the elements are being shifted cyclically. But the biggest question is why gcd is taken? Can someone explain this? Why we are running first loop gcd times?
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
Can someone please tell why will we increment by 1 in i in next set??????
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
loved your explanation
thanks a lot, brother.
why gcd please explain?
great job
well explained
really helpful
thanks a lot ......truly the best explanation
You're Welcome :)
sir I have doubt can we apply juggling algo for rotating array to right side
Thank you. Made it simple
You're Welcome !
excellent excellent awesome
does this work if k does not divide n?
explain ar=[1,2,3,4,5,6,7] where d is not becoming equal to i in array size that is in A[j] j becomes greater than 7
0 0 (0+2)%7=2
0 2 (2+2)%7=4
0 4 (4+2)%7=6
0 6 (6+2)%7=1
0 8 (8+2)%7=3 till now also d is not becoming equal to i so this is not going to happen ?
you sir are the best... this video was very helpful !! Thank you so much! Beautiful explanation :)
Thank you so much, Comments like this keep's me motivated to make more tutorials :)
Can someone tell me what is the main intuition behind this algo? Like for example, why are we taking gcd for number of sets?
why no of sets are not equal to min(n,d%n)??
Thanks for the explanation,you helped me well...can I ask which video editor are you using?
// Complete the rotLeft function below.
vector rotLeft(vector a, int d) {
int i,l=a.size();
vector b;
for(i=0;i
So what about n=7 and k=2. The GCD will be 1 and this algorithm will fail. Am I right?
NO! there will be one set and numbers will be shuffled to right places within the array! try to work it out.
I am getting same problem
Is this a limitation of juggling algorithm?..please help someone
for gcd = 1 the for loop will be
for(i =0; i < 1; i++) //i < gcd(7,2) i.e. i < 1
{
j = i // here j will get a value 0 since i is 0 in first and only pass
temp = a[j] // temp = a[0]
while (1)
{
d = (j + k )%n //k =2 therefore d will be 2
i guess you followed me till here... now i will give you the iterations here on
let the array be [1,2,3,4,5,6,7]
iteration 1:
d = 2, j = 0 a[j] = a[d]
a = 3,2,3,4,5,6,7 temp = 1, j = 2
iteration 2:
d = 4, j = 2 a[j] = a[d]
a = 3,2,5,4,5,6,7 temp = 1, j = 4
iteration 3:
d = 6, j = 4 a[j] = a[d]
a = 3,2,5,4,7,6,7 temp = 1, j = 6
iteration 4:
d = 8%7 = 1 , j = 6 a[j] = a[d]
a = 3,2,5,4,7,6,2 temp = 1, j = 1
iteration 5:
d = 3, j = 1 a[j] = a[d]
a = 3,4,5,4,7,6,2 temp = 1, j = 3
iteration 6:
d = 5, j = 3 a[j] = a[d]
a = 3,4,5,6,7,6,7 temp = 1, j = 5
now d =7%7 = 0 //hence d == i is true
and the while loop breaks
and a[j] = temp
that is a[5] = 1
hence the array becomes 3,4,5,6,7,1,2
So the above code works just fine... hope you got it
No it is not a limitation. I will give you an example here. Say we want to left shift 1 2 3 4 5 6 7 (with n = 7 and k = 2)
Since GCD is 1, yes there will be only one iteration. But in that 1 iteration, complete array would be done.
i = 0, temp = 1
j = 0, d = 2 --> a[0] = a[2] --> 3 2 3 4 5 6 7
j = 2, d = 4 --> a[2] = a[4] --> 3 2 5 4 5 6 7
j = 4, d = 6 --> a[4] = a[6] --> 3 2 5 4 7 6 7
j = 6, d = 1 (= (j + k) % n = (6 + 2) % 7) --> a[6] = a[1] --> 3 2 5 4 7 6 2
j = 1, d = 3 --> a[1] = a[3] --> 3 4 5 4 7 6 2
j = 3, d = 5 --> a[3] = a[5] --> 3 4 5 6 7 6 2
j = 5, d = 0 --> a[5] = temp because d == i --> 3 4 5 6 7 1 2
So, when j = 6, that computation of the d using modulus makes the algorithm to cycle around the array within the same set i
@@RAHULRAI-qk4ku thanks bro
You are the best.
When I submitted this solution in Leetcode(189), for the input-[1,2,3] when k=4, the accepted output in leetcode is [3,1,2] but the output from this code is [2,3,1]. The above solution needs one more condition to make it complete- if(k>n) k-=n
If you first put as first line k= k%n, does it work?
What about even elements and odd rotations and vice versa?
Beautifull! What's the time complexity?
You can also see this video for juggling algorithm.. very crisp and clear video
ua-cam.com/video/uM8z15xZVEI/v-deo.html
what is the point of doing (j+k)%n
Sir,
Do you know what is block swap rotation of array?
Explanation is as smooth as the butter on an oily surface....
thank you so much
is this algo applicable for right rotation also ?
Excellent
best explaination 100000000000
The hard part of juggling algorithmis when gcd != k. Here both the cases explained have k=gcd.
best explanation:)
Glad it was helpful!
Best video
static int[] rotLeft(int[] a, int d) {
int temp=0,i=0;
while(d>0){
temp=a[0];
for(i=0;i
Hey, help me trace it when gcd is 1?
That will run fine
Gcd is 1 means
K=1
Then no of set is 1
Okay then lets move to inner while loop (when i=0)
j=i=0
Then d=(j+k)%n => d=(0+1)%n=0
Then inside while loop
If d is equal to i then break the loop
Here d==0==i
Then inner while loop will stop
Then a(j)=temp
Thank you!
You're Welcome
Thanks
can you make a video on complexity?
Can someone trace for n=10 and k=4
Great!!!
thankyou....
please make a video on maths behind it...read first explanation of this link and explain it...i'm not able to get it..
link is
stackoverflow.com/questions/23321216/rotating-an-array-using-juggling-algorithm
Explanation is good but little difficult to follow as he talks without a pause.