# [Java] O(n) time, O(1) memory, using Euclidean algorithm

• ``````public class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
if (n == 0) return;

k = k % n;
if (k == 0) return;

int gcd = gcd(n, k);

// Do 'gcd' times rotation to the right
// Each element will be touched only once -> O(n) time complexity
for (int i = 0; i < gcd; i++) {
// Remember last element
int lastIndex = n-1 - i;
int last = nums[lastIndex];

// Rotate right
int j = lastIndex - k;
while (j != lastIndex) {
nums[(j + k) % n] = nums[j];
j = (j - k + n) % n;
}

// Replace first element with last element
nums[(lastIndex + k) % n] = last;
}
}

// Greatest common divisor
int gcd(int a, int b) {
if (b > a) return gcd(b, a);
// a >= b
if (a % b == 0) return b;
return gcd(b, a%b);
}
}``````

• Wow, nice algorithm. Can I know why rotate 'gcd' times?

• you can try [1,2,3,4,5,6] , k =2. And you will know why you need 'gcd' times.

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