CODEWITHSUNDEEP
arraysalgorithm
John
John

Reputation: 91

rotate array and number of cycles confusion

the problem is Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements. the solution (juggling method) is here http://www.geeksforgeeks.org/array-rotation/. What confuse me is why the number of cycles is gcd of n and d. Does any one know the proof with examples?

Upvotes: 1

Views: 226

Answers (2)

AnotherGeek
AnotherGeek

Reputation: 894

Basically what the developer try to do is

    Tmp = arr[0]
    for(i=0; i<n-1;i++){
     arr[i*d % n] = arr[(i+1)*d % n]
}
    arr[n-1] = arr[d-1]

Where GCD(n,d)=1 the program works fine, example (n,d)= (5,2)

Tmp = arr[0]
arr[0]= arr[2]
arr[2]= arr[4]
arr[4]= arr[1]
arr[1]= arr[3]

arr[3]= arr[5]

But when GCD(n,d)>1 here start the problem, example (6,2)

Tmp = arr[0]
arr[0]= arr[2]
arr[2]= arr[4]
arr[4]= arr[0] 
arr[0]= arr[2] // probleme because we are not able to go throw each element so we should break from the loop

Since n / GCD(6,2) = 3 we are able to only modify the first three element correctly, so he put in the loop the condition that if we come back to the first element he break from the while and increment the starting element by 1 so in the next iteration he modify arr[1],arr[3],arr[5]

Upvotes: 0

Tejash Desai
Tejash Desai

Reputation: 466

why the number of cycles is gcd of n and d

So that the number of cycles is perfectly divides both! If 'c' is the number of cycles involved, then n should be perfectly divisible by c i.e. n = xc, similarly, d = yc.

Now, in the algorithm, x is the number of sets made in the array and y is the number of steps (or iterations) performed. Check and confirm this in the given example.

The main purpose of choosing GCD is so that x and y are integers and not some float values.

Upvotes: 1

Related Questions