# Rotate An Integer Array with an O(n) algorithm [closed]

Write a function that rotates an integer array by a given number k. k elements from the end should move to the beginning of array, and all other elements should move to right to make the space.

The rotation should be done in-place.

Algorithm should not run in more than O(n), where n is the size of array.

Also a constant memory must be used to perform the operation.

For example,

if array is initialized with elements arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}

rotate(arr, 3) will result the elements to be {7, 8, 9, 1, 2, 3, 4, 5, 6}

rotate(arr, 6) will result the {4, 5, 6, 7, 8, 9, 1, 2, 3}

• What is meant by constant memory here? Surely it requires at least O(n) memory at a minimum just to store the array being processed making O(1) memory usage impossible. Commented Aug 22, 2017 at 17:09
• I'm voting to close this question as off-topic because questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win. There is absolutely no reason that this should be a popularity contest. Commented Aug 22, 2017 at 17:36
• Voted to close. From the popularity-contest wiki (here), "Gives freedom to entrants to decide what to do in crucial parts and incentivizes them to use this freedom." I don't think leaving the challenge open to any algorithm counts as encouraging creativity for such a simple challenge, at least not to the extent that it works as a popcon. This would be more suited as a code-golf challenge. Commented Aug 22, 2017 at 20:56

## C (104)

void reverse(int* a, int* b)
{
while (--b > a) {
*b ^= *a;
*a ^= *b;
*b ^= *a;
++a;
}
}

void rotate(int *arr, int s_arr, int by)
{
reverse(arr, arr+s_arr);
reverse(arr, arr+by);
reverse(arr+by, arr+s_arr);
}


Minified:

v(int*a,int*b){while(--b>a){*b^=*a;*a^=*b;*b^=*a++;}}r(int*a,int s,int y){v(a,a+s);v(a,a+y);v(a+y,a+s);}

• You should have written the while loop condition as a <-- b Commented Nov 6, 2014 at 9:40
• There used to be a time when C programs won popularity contests... Commented May 2, 2015 at 2:32
• You are the best! How elegant and optimized.. Could you do this with bit array?
– user69099
Commented Oct 2, 2017 at 7:18

# APL (4)

¯A⌽B

• A is the number of places to rotate
• B is the name of the array to be rotated

I'm not sure if APL actually required it, but in the implementation I've seen (the internals of) this would take time proportional to A, and constant memory.

• +1 if this were golf :) Commented Jan 17, 2014 at 6:03
• It doesn't do it in place though. Commented Nov 6, 2014 at 10:03
• @marinus: It certainly does in the implementations I've seen. Commented Nov 6, 2014 at 14:28
• How is this a function? Could be {⍵⌽⍨-⍺} or {⌽⍺⌽⌽⍵}. In NARS2000 it may be elegantly written as ⌽⍢⌽.
Commented Dec 10, 2015 at 3:00

Here is a long winded C version of Colin's idea.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
int t;
if (a < b) {
t = b; b = a; a = t;
}
while (b != 0) {
t = a%b;
a = b;
b = t;
}
return a;
}

double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int s_arr = sizeof(arr)/sizeof(double);

/* We assume 1 <= by < s_arr */
void rotate(double *arr, int s_arr, int by) {
int i, j, f;
int g = gcd(s_arr,by);
int n = s_arr/g;
double t_in, t_out;

for (i=0; i<g; i++) {
f = i;
t_in = arr[f + s_arr - by];
for (j=0; j<n; j++) {
t_out = arr[f];
arr[f] = t_in;
f = (f + by) % s_arr;
t_in = t_out;
}
}
}

void print_arr(double *arr, int s_arr) {
int i;
for (i=0; i<s_arr; i++) printf("%g ",arr[i]);
puts("");
}

int main() {
double *temp_arr = malloc(sizeof(arr));
int i;

for (i=1; i<s_arr; i++) {
memcpy(temp_arr, arr, sizeof(arr));
rotate(temp_arr, s_arr, i);
print_arr(temp_arr, s_arr);
}
}

• It doesn't look like a constant memory solution, is it? Commented Jan 9, 2014 at 20:45
• Yes it is a constant memory solution. The "malloced" stuff is a temporary copy of the array so that I can copy the original data into it again and again, so that I can test for different rotation amounts. Commented Jan 9, 2014 at 22:20
• What does the actual rotate is the function "rotate." It uses 5 integers and two doubles. It also calls a function "gcd" which uses one integer, and uses at most O(log(n)) operations. Commented Jan 9, 2014 at 22:24
• Got it. I upped your answer. Commented Jan 11, 2014 at 6:25
• @StephenMontgomery-Smith -- how is this O(log(n)) operations. Look at by being 1, your j' loop is s_arr/g or N -- this is O(N) operations Commented Jan 17, 2014 at 5:57

## C

Not sure what the criteria is, but since I had fun with the algorithm, here is my entry:

void rotate(int* b, int size, int shift)
{
int *done;
int *p;
int i;
int saved;
int c;

p = b;
done = p;
saved = *p;
for (i = 0; i < size; ++i) {
c = saved;
p += shift;
if (p >= b+size) p -= size;
saved = *p;
*p = c;
if (p == done) {
p += 1;
done = p;
saved = *p;
}
}
}


I'll golf it for a good measure too; 126 bytes, can be made shorter:

void r(int*b,int s,int n){int*d,*p,i,t,c;d=p=b;t=*p;for(i=0;i<s;++i){c=t;p+=n;if(p>=b+s)p-=s;t=*p;*p=c;if(p==d){d=++p;t=*p;}}}


I don't see very many C++ solutions here, so I figured I'd try this one since it doesn't count characters.

This is true "in-place" rotation, so uses 0 extra space (except technically swap and 3 ints) and since the loop is exactly N, also fulfills the O(N) complexity.

template <class T, size_t N>
void rot(std::array<T,N>& x, int shift)
{
size_t base=0;
size_t cur=0;
for (int i = 0; i < N; ++i)
{
cur=(cur+shift)%N; // figure out where we are going
if (cur==base)     // exact multiple so we have to hit the mods when we wrap
{
cur++;
base++;
}
std::swap(x.at(base), x.at(cur)); // use x[base] as holding area
}
}

• Note: I purposely did not use std::rotate because that kind of defeats the purpose Commented Jan 17, 2014 at 5:45

If you perform each of the possible cycles of rotations by n in turn (there are GCD(n, len(arr)) of these), then you only need a single temporary copy of an array element and a few state variables. Like this, in Python:

from fractions import gcd

def rotate(arr, n):
total = len(arr)
cycles = gcd(n, total)
for start in range(0, cycles):
cycle = [i % total for i in range(start, abs(n * total) / cycles, n)]
stash = arr[cycle[-1]]
for j in reversed(range(1, len(cycle))):
arr[cycle[j]] = arr[cycle[j - 1]]
arr[cycle[0]] = stash

• I think you have the right idea, but your cycle variable is non-constant sized. You'll have to generate this array as you go. Commented Jan 4, 2014 at 5:03

C (137 characters)

#include <stdio.h>

void rotate(int * array, int n, int k) {
int todo = (1<<n+1)-1;
int i = 0, j;
int tmp = array[0];

while (todo) {
if (todo & 1<<i) {
j = (i-k+n)%n;
array[i] = todo & 1<<j ? array[j] : tmp;
todo -= 1<<i;
i = j;
} else tmp = array[++i];
}
}

int main() {
int a[] = {1,2,3,4,5,6,7,8,9};
rotate(a, 9, 4);
for (int i=0; i<9;i++) printf("%d ", a[i]);
printf("\n");
}


Function rotate minified to 137 characters:

void r(int*a,int n,int k){int m=(1<<n+1)-1,i=0,j,t=a[0];while(m)if(m&1<<i){j=(i-k+n)%n;a[i]=(m&1<<j)?a[j]:t;m-=1<<i;i=j;}else t=a[++i];}


Factor has a built-in type for rotatable arrays, <circular>, so this is actually a O(1) operation:

: rotate ( circ n -- )
neg swap change-circular-start ;

IN: 1 9 [a,b] <circular> dup 6 rotate >array .
{ 4 5 6 7 8 9 1 2 3 }
IN: 1 9 [a,b] <circular> dup 3 rotate >array .
{ 7 8 9 1 2 3 4 5 6 }


A less cheatish Factor equivalent of Ben Voigt's impressive C solution:

: rotate ( n s -- )
reverse! swap cut-slice [ reverse! ] bi@ 2drop ;

IN: 7 V{ 0 1 2 3 4 5 6 7 8 9 } [ rotate ] keep .
V{ 3 4 5 6 7 8 9 0 1 2 }


# JavaScript 45

Went for golf anyway because I like golf. It is at maximum O(N) as long as t is <= size of the array.

function r(o,t){for(;t--;)o.unshift(o.pop())}


To handle t of any proportion in O(N) the following can be used (weighing in at 58 characters):

function r(o,t){for(i=t%o.length;i--;)o.unshift(o.pop())}


Doesn't return, edits the array in place.

• +1 for r(o,t) => rot Commented Jan 20, 2016 at 18:46

## REBEL - 22

/_(( \d+)+)( \d+)/$3$1


Input: k expressed as a unary integer using _ as a digit, followed by a space, then a space-delimited array of integers.

Output: A space, then the array rotated.

Example:

___ 1 2 3 4 5/_(( \d+)+)( \d+)/$3$1


Final state:

 3 4 5 1 2


Explanation:

At each iteration, it replaces one _ and an array [array] + tail with tail + [array].

Example:

___ 1 2 3 4 5
__ 5 1 2 3 4
_ 4 5 1 2 3
3 4 5 1 2

• I don't think this is O(n). Copying an array is O(n), and you do that n times. Commented Jan 15, 2014 at 1:21

# Java

public static void rotate(int[] arr, int by) {
int n = arr.length;
int i = 0;
int j = 0;
while (i < n) {
int k = j;
int value = arr[k];
do {
k = (k + by) % n;
int tmp = arr[k];
arr[k] = value;
value = tmp;
i++;
} while (k != j);
j++;
}
}


Demo here.

Minified Javascript, 114:

function rotate(e,r){n=e.length;i=0;j=0;while(i<n){k=j;v=e[k];do{k=(k+r)%n;t=e[k];e[k]=v;v=t;i++}while(k!=j);j++}}


This is actually θ(n), as the split is θ(k) and the join is θ(n-k). Not sure about memory though.

rotate 0 xs = xs
rotate n xs | n >= length xs = rotate (nmod(length xs)) xs
| otherwise = rotate' n xs

rotate' n xs = let (xh,xt) = splitAt n xs in xt++xh


# Python 3

from fractions import gcd
def rotatelist(arr, m):
n = len(arr)
m = (-m) % n # Delete this line to change rotation direction
for i0 in range(gcd(m, n)):
temp = arr[i0]
i, j = i0, (i0 + m) % n
while j != i0:
arr[i] = arr[j]
i, j = j, (j + m) % n
arr[i] = temp


Constant memory
O(n) time complexity

## Python

def rotate(a, n): a[:n], a[n:] = a[-n:], a[:-n]

• Will this use constant memory? Commented Jan 4, 2014 at 3:10
• Hmm... not sure. Commented Jan 4, 2014 at 3:10
• It's not a constant memory operation. Commented Jan 4, 2014 at 3:10
• Shucks. Good call... Commented Jan 4, 2014 at 3:13

python

   import copy
def rotate(a, r):
c=copy.copy(a);b=[]
for i in range(len(a)-r):   b.append(a[r+i]);c.pop();return b+c

• Copying the array is not constant space. @MadisonMay's answer does essentially the same thing as this code with many fewer characters. Commented Jan 17, 2014 at 6:27

vb.net O(n) (not Constant memory)

Function Rotate(Of T)(a() As T, r As Integer ) As T()
Dim p = a.Length-r
Return a.Skip(p).Concat(a.Take(p)).ToArray
End Function


### Ruby

def rotate(arr, n)
arr.tap{ (n % arr.size).times { arr.unshift(arr.pop) } }
end


## C (118)

Probably was a bit too lenient with some of the specifications. Uses memory proportional to shift % length. Also able to rotate in the opposite direction if a negative shift value is passed.

r(int *a,int l,int s){s=s%l<0?s%l+l:s%l;int *t=malloc(4*s);memcpy(t,a+l-s,4*s);memcpy(a+s,a,4*(l-s));memcpy(a,t,4*s);}


# Python 2, 57

def rotate(l,n):
return l[len(l)-n:len(l)]+l[0:len(l)-n]


If only l[-n:len(l)-n] worked like I'd expect it to. It just returns [] for some reason.

def r(a,n): return a[n:]+a[:n]


Could someone please check if this actually meets the requirements? I think it does, but it I haven't studied CS (yet).

## C++, 136

template<int N>void rotate(int(&a)[N],int k){auto r=[](int*b,int*e){for(int t;--e>b;t=*b,*b++=*e,*e=t);};r(a,a+k);r(a+k,a+N);r(a,a+N);}


# Java

Swap the last k elements with the first k elements, and then rotate the remaining elements by k. When you have fewer than k elements left at the end, rotate them by k % number of remaining elements. I don't think anyone above took this approach. Performs exactly one swap operation for every element, does everything in place.

public void rotate(int[] nums, int k) {
k = k % nums.length; // If k > n, reformulate
rotate(nums, 0, k);
}

private void rotate(int[] nums, int start, int k) {
if (k > 0) {
if (nums.length - start > k) {
for (int i = 0; i < k; i++) {
int end = nums.length - k + i;
int temp = nums[start + i];
nums[start + i] = nums[end];
nums[end] = temp;
}
rotate(nums, start + k, k);
} else {
rotate(nums, start, k % (nums.length - start));
}
}
}


# Perl 5, 42 bytes

sub r{$a=pop;map{unshift@$a,pop@\$a}1..pop}
`

Try it online!

Subroutine takes the distance to rotate as the first parameter and a reference to the array as the second. Run time is constant based on the distance of the rotation. Array size does not affect run time. Array is modified in place by removing an element from the right and putting it on the left.