# 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. – Wheat Wizard Aug 22 '17 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. – DJMcMayhem Aug 22 '17 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. – mbomb007 Aug 22 '17 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 – justhalf Nov 6 '14 at 9:40
• There used to be a time when C programs won popularity contests... – Anubian Noob May 2 '15 at 2:32
• You are the best! How elegant and optimized.. Could you do this with bit array? – user69099 Oct 2 '17 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 :) – Glenn Teitelbaum Jan 17 '14 at 6:03
• It doesn't do it in place though. – marinus Nov 6 '14 at 10:03
• @marinus: It certainly does in the implementations I've seen. – Jerry Coffin Nov 6 '14 at 14:28
• How is this a function? Could be {⍵⌽⍨-⍺} or {⌽⍺⌽⌽⍵}. In NARS2000 it may be elegantly written as ⌽⍢⌽. – Adám Dec 10 '15 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? – microbian Jan 9 '14 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. – Stephen Montgomery-Smith Jan 9 '14 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. – Stephen Montgomery-Smith Jan 9 '14 at 22:24
• Got it. I upped your answer. – microbian Jan 11 '14 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 – Glenn Teitelbaum Jan 17 '14 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 – Glenn Teitelbaum Jan 17 '14 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] = 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. – Keith Randall Jan 4 '14 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;

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;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 – Conor O'Brien Jan 20 '16 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. – Ben Voigt Jan 15 '14 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++}}


# Haskell

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? – SztupY Jan 4 '14 at 3:10
• Hmm... not sure. – Madison May Jan 4 '14 at 3:10
• It's not a constant memory operation. – microbian Jan 4 '14 at 3:10
• Shucks. Good call... – Madison May Jan 4 '14 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. – Blckknght Jan 17 '14 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.