Move an array to the left by n positions without allocating more memory

move_left.c

#include <stdio.h>

void swap(int *a, int *b) {
  int tmp = *a; *a = *b; *b = tmp;
}

void move_left(int a[], size_t size, int n) {
  n = ((n % (int)size) + size) % size;
  size_t remaining_size = size;
  for(size_t i=0; i<size-1; i++) {
    if (i+n == size) {
      n = (n - remaining_size % n) % n;
      remaining_size = size - i;
    }
    swap(a+i, a+i+n);
  }
}

int main(int argc, char* argv[]) {
  int a[] = {0,1,2,3,4,5,6,7,8,9};
  size_t size = sizeof(a)/sizeof(a[0]);
  move_left(a, size, 7);
  for (int i=0; i<size; i++) printf("%d ", a[i]);
  printf("\n");
  return 0;
}

move_left_cpp11.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <numeric>

using namespace std;

template<typename T>
void move_left(vector<T> &a, int n) {
  size_t size = a.size();
  n = ((n % (int)size) + size) % size;
  for(auto i = a.begin(), end=a.end(); i<end-1; i++) {
    if (end - i == n) {
      n = (n - size % n) % n;
      size = end - i;
    }
    iter_swap(i, i+n);
  }
}

int main(int argc, char* argv[]) {
  if (argc != 2) {
    cout << "Usage: " << argv[0] << " COUNT" << endl;
    return 1;
  }
  int n = stoi(argv[1]);
  
  vector<int> a = vector<int>(0);
  int i;
  while (cin >> i) a.push_back(i);

  move_left(a, n);

  for (auto e: a) cout << e << " ";
  cout << endl;
  return 0;
}

move_left_generic.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <numeric>

using namespace std;

template<typename T>
void move_left(vector<T> &a, int n) {
  size_t size = a.size();
  n = ((n % (int)size) + size) % size;
  for(auto i = a.begin(), end=a.end(); i<end-1; i++) {
    if (end - i == n) {
      n = (n - size % n) % n;
      size = end - i;
    }
    iter_swap(i, i+n);
  }
}

int main(int argc, char* argv[]) {
  if (argc != 2) {
    cout << "Usage: " << argv[0] << " COUNT" << endl;
    return 1;
  }
  int n = stoi(argv[1]);
  
  vector<int> a = vector<int>(0);
  int i;
  while (cin >> i) a.push_back(i);

  move_left(a, n);

  for (auto e: a) cout << e << " ";
  cout << endl;
  return 0;
}

move_left_recursive.c

#include <stdio.h>

void swap(int *a, int *b) {int tmp = *a; *a = *b; *b = tmp;}

void move_left(int *a, size_t size, int n) {
  n = ((n % (int)size) + size) % size;
  if (n == 0 || size <= 1) return;
  for(size_t i=0; i<size-n; i++) swap(a+i, a+i+n);
  move_left(a+size-n, n, n-size%n);
}

int main(int argc, char* argv[]) {
  int a[] = {0,1,2,3,4,5,6,7,8,9};
  size_t size = sizeof(a)/sizeof(a[0]);
  move_left(a, size, -7);
  for (int i=0; i<size; i++) printf("%d ", a[i]);
  printf("\n");
  return 0;
}

требования.md

Упражнение

В этой задаче вам нужно реализовать функцию, которая сдвигает содержимое массива влево на заданное число позиций (циклический сдвиг).

На вход функция принимает массив, его размер и величину сдвига. Например, если на вход функции подан массив: int а[] = { 1, 2, 3, 4, 5 }; и требуется циклически сдвинуть его влево на 2 позиции, то на выходе мы получим числа в таком порядке: 3, 4, 5, 1, 2.

Обратите внимание, что величина сдвига может быть нулевой, а может быть и больше размера массива, все эти случаи нужно учесть.

Требования к реализации

вам нужно реализовать только функцию циклического сдвига. При этом она не должна вводить или выводить что-либо. При решении этой задачи вы можете определять любые вспомогательные функции, если они вам нужны. Реализовывать функцию main не нужно. Предполагается, что вам не потребуется дополнительная память, а именно: массивы и стандартные контейнеры. Пользоваться стандартными алгоритмами и контейнерами не разрешается, даже если вы с ними знакомы.

Рекомендация

перед тем, как начать кодировать решение этой задачи, продумайте алгоритм, который вы будете использовать. В данной задаче не проверяется эффективность этого алгоритма (в разумных пределах).

Подсказка

вам может потребоваться оператор % для вычисления остатка. Наиболее простая реализация этой функции сдвигает массив на один элемент за проход. Наиболее простая реализация несколько раз использует функцию, которая переставляет элементы массива в обратном порядке.