# My three way to solve this problem, the first way is interesting(JAVA)

• Method 1: ( Interesting way, O(n) time cost, O(1) space cost)

``````public class Solution {
public void rotate(int[] nums, int k) {
if(nums.length <= 1){
return;
}
//step each time to move
int step = k % nums.length;
//find GCD between nums length and step
int gcd = findGcd(nums.length, step);
int position, count;

//gcd path to finish movie
for(int i = 0; i < gcd; i++){
//beginning position of each path
position = i;
//count is the number we need swap each path
count = nums.length / gcd - 1;
for(int j = 0; j < count; j++){
position = (position + step) % nums.length;
//swap index value in index i and position
nums[i] ^= nums[position];
nums[position] ^= nums[i];
nums[i] ^= nums[position];
}
}
}

public int findGcd(int a, int b){
return (a == 0 || b == 0) ? a + b : findGcd(b, a % b);
}

}
``````

Method 2:( 3 reverse thinking, O(n) time cost, O(1) space cost)

``````public class Solution {
public void rotate(int[] nums, int k) {
if(nums.length <= 1){
return;
}
//step each time to move
int step = k % nums.length;
reverse(nums,0,nums.length - 1);
reverse(nums,0,step - 1);
reverse(nums,step,nums.length - 1);
}

//reverse int array from n to m
public void reverse(int[] nums, int n, int m){
while(n < m){
nums[n] ^= nums[m];
nums[m] ^= nums[n];
nums[n] ^= nums[m];
n++;
m--;
}
}
}
``````

Method 3:( Normal way, O(n) time cost, O(k % nums.length) space cost)

``````public class Solution {
public void rotate(int[] nums, int k) {
if(nums.length <= 1){
return;
}
//step each time to move
int step = k % nums.length;
int[] tmp = new int[step];
for(int i = 0; i < step; i++){
tmp[i] = nums[nums.length - step + i];
}
for(int i = nums.length - step - 1; i >= 0; i--){
nums[i + step] = nums[i];
}
for(int i = 0; i < step; i++){
nums[i] = tmp[i];
}

}

}``````

• This post is deleted!

• Good job, similarly, I implemented the first method and the second method is like a magic, how can it be? :P

The following is my code using method 1.

``````class Solution {
public:
int gcd(int a, int b)
{
for (;;)
{
if (a == 0) return b;
b %= a;
if (b == 0) return a;
a %= b;
}
}

int lcm(int a, int b)
{
int temp = gcd(a, b);

return temp ? (a / temp * b) : 0;
}

void rotate(int nums[], int n, int k)
{
int cycnum = 0,t=0, temp = 0, temp1 = 0, c = 1, place = 0, i = 0, j = 0;

if (!n || !(k%n))
return;
k = k%n;

cycnum=lcm(k,n)/k; //steps for each cycle
c=n/cycnum; //nums of cycles
while (c--)
{
i = j;
t = cycnum;
temp = nums[i];
while (t--)
{
place = (i + k) % n;
temp1 = nums[place];
nums[place] = temp;
temp = temp1;
i = place;
}

j++;
}
}};``````

• Good implementation and very appreciate for your praising! Actually right shift k steps will move right most k elements to the left side. Here is an example of the second method:

with n = 7 and k = 3, the array [1,2,3,4,5,6,7]

1. reverse the whole array -> [7,6,5,4,3,2,1]

2. reverse 1 to k elements -> [5,6,7,4,3,2,1]

3. reverse k+1 to the end -> [5,6,7,1,2,3,4]

• what are count and gcd meant for please elaborate ?

• Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain:

1. suppose k = 3:

GCD = gcd(3,8) = 1, which means there is only one path.

Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps)

Then we can simulate the process of the algorithm,

path0(each time swap index0 element and indexPosition element):

[1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> [7,2,3,1,5,6,4,8](position = 1) -> [2,7,3,1,5,6,4,8](position = 4) -> [5,7,3,1,2,6,4,8](position = 7) -> [8,7,3,1,2,6,4,5](position = 2) -> [3,7,8,1,2,6,4,5](position = 5) -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5]

1. suppose k = 2:

Similary, GCD = 2, which means there are 2 paths.

count = 3, which means we need 3 swaps to finish each path.

Give the process:

path0(swap index0 and position element):

[1,2,3,4,5,6,7,8](position = 2) -> [3,2,1,4,5,6,7,8](position = 4) ->[5,2,1,4,3,6,7,8](position = 6) -> [7,2,1,4,3,6,5,8] -> path0 finished

Then we continue processing path1(swap index1 and position element):

[7,2,1,4,3,6,5,8](position = 3) -> [7,4,1,2,3,6,5,8](position = 5) -> [7,6,1,2,3,4,5,8](position = 7) ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]

• Detail explain of method 1:

Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain:

1.suppose k = 3:

GCD = gcd(3,8) = 1, which means there is only one path.

Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps)

Then we can simulate the process of the algorithm,

path0(each time swap index0 element and indexPosition element):

[1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> [7,2,3,1,5,6,4,8](position = 1) -> [2,7,3,1,5,6,4,8](position = 4) -> [5,7,3,1,2,6,4,8](position = 7) -> [8,7,3,1,2,6,4,5](position = 2) -> [3,7,8,1,2,6,4,5](position = 5) -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5]

2.suppose k = 2:

Similary, GCD = 2, which means there are 2 paths.

count = 3, which means we need 3 swaps to finish each path.

Give the process:

path0(swap index0 and position element):

[1,2,3,4,5,6,7,8](position = 2) -> [3,2,1,4,5,6,7,8](position = 4) ->[5,2,1,4,3,6,7,8](position = 6) -> [7,2,1,4,3,6,5,8] -> path0 finished

Then we continue processing path1(swap index1 and position element):

[7,2,1,4,3,6,5,8](position = 3) -> [7,4,1,2,3,6,5,8](position = 5) -> [7,6,1,2,3,4,5,8](position = 7) ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]

• thanks a lot,your explanation is very clear,but what i did not understand in the first place is why are you calculating gcd to find the paths & Count =(n/gcd)-1 to find the steps

• I found given a number N and a move steps K. Start from any position P0 of N, keep move right position K by K, the position will back to original one(P0) after N / gcd(N,K) = (count + 1)times.

In this question every element(N elements) in the array should move right K position. And N = gcd(N,K) * (count + 1), means we can divided N elements into gcd(N,K) differents part(each part has a move path), move every element in each part right K position, then we get the result.

• i also do not undanstand,can you explain it?

• I have explained it before, you could see comment before you, hope it helpful.

• thanks again took me a quite a long time to understand (nearly 2 hours),basic high school math problem

• nice solution

• public class Solution {
public void rotate(int[] nums, int k) {
if(nums.length <= 1){
return;
}
//step each time to move
int step = k % nums.length;
int[] tmp = new int[step];
for(int i = 0; i < step; i++){
tmp[i] = nums[nums.length - step + i];
}
int n = nums.length;
for(int i = nums.length - step - 1; i >= 0; i--){
nums[n--] = nums[i];
}
for(int i = 0; i < step; i++){
nums[i] = tmp[i];
}

``````}
``````

}

find error
for(int i = nums.length - step - 1; i >= 0; i--){
nums[n--] = nums[i];
}

java.lang.ArrayIndexOutOfBoundsException: 7

• Hi, here is another interesting solution different from all of yours. It kind of shares some basic idea with your 1st solution. But I don't compute GCD and count of steps for each path. I just let it jumps from one path to another after finishing the previous path. And I didn't use swap() to process a path. Hope you are interested in it. :)

//Time complexity O(n), extra space cost O(1)

``````public class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
if(k<=0) return;
int index = k, loopHead = 0, curr = nums[0];
//1. index is the index of the element we will update in each iteration.
//2. loopHead is head of a loop (if exist) for index since each time we
// move index k steps further.
//3. curr is the value got from previous iteration nums[preIndex] and
//for updating nums[index]
for(int count=0;count<nums.length;count++){
nums[index] = curr; //set the value of loopHead.
loopHead++; //move 1 step further to jump out of loop
curr = nums[++index]; //This is the head of new loop
index = (index+k)%nums.length;
}
else{ //each time go k steps further
int tmp = nums[index];
nums[index] = curr;
curr = tmp;
index = (index+k)%nums.length;
}
}
}
}``````

• Nice!! ........

• very nice solutions!

• Won't the XOR method for number swap fail for equal numbers?

• example: 5 XOR 5 = 0; 5 XOR 0 = 5; 5 XOR 0 = 5;
It won't fail.

• Can anyone please explain why the last step in Method 3 have to be:
for(int i = 0; i < step; i++){
nums[i] = tmp[i];
}
instead of simply assign tmp to nums by: nums = tmp;

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.