public void rotate3(final int[] nums, int k) {
        final int n = nums.length;

        if (n <= 1) {
            return;
        }

        while (n < k) {
            k = k % n;
        }

        if (n == k) {
            return;
        }

        // right rotate k == left rotate(n - k)
        k = n - k;

        // current location
        int j;
        // next location
        int d;
        // store the overwritten number
        int tmp;
        for (int i = 0; i < gcd(n, k); i++) {
            // initialize
            tmp = nums[i];
            j = i;

            while (true) {
                d = j + k;
                if (d >= n) {
                    d = d - n;
                }
                if (d == i) {
                    break;
                }
                nums[j] = nums[d];
                j = d;
            }
            // at this point, j moved to the last possible location
            nums[j] = tmp;
        }

    }