Initial commit.HEADmain

1 files changed, 39 insertions, 0 deletions

diff --git a/top-interview-questions/easy/array/03_rotate_array.cc b/top-interview-questions/easy/array/03_rotate_array.cc
new file mode 100644
index 0000000..19f66dd
--- /dev/null
+++ b/top-interview-questions/easy/array/03_rotate_array.cc
@@ -0,0 +1,39 @@
+class Solution {
+public:
+    // Works, but it's slow.
+    /*int gcd(int a, int b) {
+        if (a == 0) return b;
+        if (b == 0) return a;
+        if (a == b) return a;
+        if (a  > b) return gcd(a-b, b);
+        else        return gcd(a, b-a);
+    }*/
+
+    // Much faster than the above implementation.
+    int gcd(int a, int b) {
+        if (b == 0) return a;
+        else        return gcd(b, a%b);
+    }
+
+    void rotate(vector<int>& nums, int k) {
+        const size_t N = nums.size();
+        if ((N <= 1) || (k == 0)) {
+            return;
+        }
+        // Original algorithm only works for (N,k) coprime.
+        // Break the cycles when we complete a loop around the array.
+        const int gcdNk = gcd(N,k);
+        const int steps = (gcdNk != 1) ? (N / gcdNk) : N;
+        int start = -1;
+        for (size_t n = 0; n < N; n += steps) {
+            ++start;
+            int i = start;
+            int i_val = nums[i];
+            for (size_t s = 0; s < steps; ++s) {
+                const int next = (i+k) % N;
+                std::swap(i_val, nums[next]);
+                i = next;
+            }
+        }
+    }
+};