class Solution {
    public static int findCheck(int k, int n) {
        int nok = n;
        do {
            if (nok % k == 0) {
                return nok / k;
            }
            nok += n;
        } while (nok / k < n);
        return n;
    }

    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n <= 1 || k % n == 0) {
            return;
        }
        k = k % n;
        int steps = 0;
        int i = 0, last = nums[0];
        int check = findCheck(k, n);
        while (++steps <= n) {
            i += k;
            if (i >= n) {
                i -= n;
            }
            int b = nums[i];
            nums[i] = last;
            last = b;
            if (steps % check == 0) {
                i++;
                last = nums[i];
            }
        }
    }
}