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.
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.
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
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
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?
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)?
# 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)
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 ?
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
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
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.
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.
bro, I just subscribed watching only this video of yours!
Hats off to your explanations!
don't stop making videos!
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
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
The best explanation for juggling algo !!!!
Best explanation of juggling algorithm.. Thank you.. ♥️♥️♥️
Wow...so much clear cut explanation...thanks
better than any arrays rotation videos available so far i understood it so damn well thnx :)
Thanks dude, and explanation is so good🔥
Only video! which explains juggling algo very well.👍
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.
clean simple and best explanation!
You can also see this video for juggling algorithm.. very crisp and clear video
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
Thanks for the concise explanation! Cheers!
very very good explanation.......... it is best explanation ever
Your explanation is precise, quick and straight to the point.
OMG sir you hit that topics so clearly, big thanks for you, help me a lot
Best explaination , was struggling to understand this,Thanks
Thanks for the explanation with the help of a beautiful insight.❤
Fabulous Explanation
Thanks a lot for this video. It was really difficult for me to understand before but after watching your video, I completely understood it.
Thanks for the explanation. Great job!
Great Explaination bro... unlimited likes
This is the best explanation.Much better than gfg. Thank you so much 🥰🥰😊😊
Great 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.
Very good explanation.....
Just a side note: The implementation you show at around 14:30 is plain ANSI-C, and nothing that needs C++.
I need to watch it one more time to understand it well
oh man you just rock it .Thanks alot
Really i'm so surprise.Because this is the best tutorial.Thank you very much.
You are welcome!
best explanation of tis algorithm. very thank u
You're Welcome :)
please also upload Block swap algorithm for array rotation
Awesome explanation... Kudos to you....
Good explanation! Thanks.
Very nicely explained . . . Thanks
Very helpful
you are a legend
Very nice 👌
well explained
good explaination
Awesome Please upload more videos based on tree and dynamic programming
Thanks, will surely do in future !!
thanks bhai...samaj me aa gaya
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
really helpful
great job
What's the intuition behind the gcd part?
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 please tell me why we calculate the GCD of n and k for finding sets ??? Please explain
thanks a lot, brother.
loved your explanation
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.
excellent excellent awesome
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?
Explanation is as smooth as the butter on an oily surface....
A nice video and a sweet voice, thank you.
best explaination 100000000000
You are the best.
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
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
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
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
You can also see this video for juggling algorithm.. very crisp and clear video
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
Nice explanation good work ...
thanks a lot ......truly the best explanation
You're Welcome :)
thank you so much
Thank you. Made it simple
You're 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
# 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)
What we will do if right rotation is asked?
Excellent
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
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
Beautifull! What's the time complexity?
You can also see this video for juggling algorithm.. very crisp and clear video
th-cam.com/video/uM8z15xZVEI/w-d-xo.html
how to use this algo for right rotation?
ADITYA KUMAR n - left rotation where n is size
Best video
does this work if k does not divide n?
best explanation:)
Glad it was helpful!
why gcd please explain?
// Complete the rotLeft function below.
vector rotLeft(vector a, int d) {
int i,l=a.size();
vector b;
for(i=0;i
sir I have doubt can we apply juggling algo for rotating array to right side
what is the point of doing (j+k)%n
What about even elements and odd rotations and vice versa?
why no of sets are not equal to min(n,d%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 ?
is this algo applicable for right rotation also ?
The hard part of juggling algorithmis when gcd != k. Here both the cases explained have k=gcd.
Sir,
Do you know what is block swap rotation of array?
can you make a video on complexity?
Thanks for the explanation,you helped me well...can I ask which video editor are you using?
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
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
Thanks
Can someone tell me what is the main intuition behind this algo? Like for example, why are we taking gcd for number of sets?
static int[] rotLeft(int[] a, int d) {
int temp=0,i=0;
while(d>0){
temp=a[0];
for(i=0;i
Great!!!
Can someone trace for n=10 and k=4
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
best