Ваша задача - сделать циклический сдвиг массива на k позиций влево на месте, с O(1) дополнительной памяти.
Вот код:
void ShiftLeft(std::vector<int> &a, int k) {
int n = a.size();
int cycles = std::gcd(n, k);
for (int start = 0; start < cycles; ++start) {
int tmp = a[start];
int i = start;
while (true) {
int next = i + k;
if (next >= n) next -= n;
if (next == start) break;
a[i] = a[next];
i = next;
}
a[i] = tmp;
}
}
Работает это так: на место элемента вставет элемент на k позиций правее. Возьмем первый элемент, запомним его в tmp, поставим на его место тот, кто там должен быть. Освободилось место, поставим на него опять того, кто там должен быть и так далее. Рано или поздно мы вернемся к первому элементу. Но там уже стоит второй. Тут можно выйти из цикла и поставить на нужное место тот, кого мы сохранили в tmp. Но мы могли обойти не весь массив, как, например в случае n=6, k=2. Начав с 0 мы тут подвинем элементы 0,2,4, но не 1,3,5. Всего будет циклов gcd(n, k), и они все идут со сдвигом 1. Поэтому можно начинать с каждого из нескольких первых элементов.
Додуматься до этого можно так: сдвиг на 1 позицию понятно как циклом while сделать-то и одной переменной tmp. А на несколько? Надо только заметить что элементы разбиваются на циклы.
Средний
