# THREE solutions O(N) time/O(1) space in c++

• solution1: double reverse
solution2: circular rotation using largest common divider
solution3: recursive

class Solution {
void reverse(vector<int>& nums, int first, int last) {
while (first < last) {
swap(nums[first++], nums[last--]);
}
}

``````    int largestCommonDivider(int x, int y) {
if (x < y) swap(x, y);  // ensure x >= 1;
while (x % y != 0) {
x %= y;
swap(x, y);
}
return y;
}

public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
if (n < 2) return;
k %= n;
if (k == 0) return;

rotate3(nums, 0, n - k, k);
}

void rotate1(vector<int>& nums, int k) {
reverse(nums, 0, nums.size() - k - 1);
reverse(nums, nums.size() - k, nums.size() - 1);
reverse(nums, 0, nums.size() - 1);
}

void rotate2(vector<int>& nums, int k) {
int n = nums.size();
int commonDivider = largestCommonDivider(n, k);
for (int start = 0; start < commonDivider; ++start) {
int valueToMove = nums[start];
for (int i = 1; i <= n/commonDivider; ++i) {
int targetPos = (i*k + start) % n;
swap(valueToMove, nums[targetPos]);
}
}
}

void rotate3(vector<int>& nums, int start, int k1, int k2) {
while (true) {
int kMin = min(k1, k2);
int kMax = max(k1, k2);
for (int i = 0; i < kMin; ++i) {
swap(nums[start + i], nums[start + i + kMax]);
}
if (k1 < k2) {
k2 -= k1;
} else if (k1 > k2) {
start += kMin;
k1 = k1 - k2;
} else {
break;
}
}
}
};``````

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