CareerCup

1. reverse the array from 0 to n-1
2. reverse the array from n- length
3. reverse the whole array (from 0 - length)

N = N % len
reverse (len-N, len-1), reverse(0, len-1), reverse(N,len-1)

Working version of java code with time complexity as O(n) and space complexity as O(1)

class Test_ArrayRotation
{
	public static void main(String args[])
	{
		int iArray[] = new int[] { 1, 2, 3, 4, 5 };
		System.out.println("Actual Array");
		PrintArray(iArray);
		RotateArray(iArray, 3);
		System.out.println("After Rotation");
		PrintArray(iArray);
	}
	
	public static void PrintArray(int inputArray[])
	{
		for(int i=1; i<=inputArray.length; i++)
			System.out.println(i + ")" + inputArray[i-1]);
		
		System.out.println("\n");
	}

	public static void RotateArray(int inputArray[], int iNoOfRotations)
	{
		int iIndex = 0;
		
		for(int i=0; i<inputArray.length; i++)
		{
			int iNewIndex = (iIndex + iNoOfRotations) % inputArray.length;
			int iValue = inputArray[iNewIndex];
			inputArray[iNewIndex] = inputArray[0];
			inputArray[0] = iValue;
			iIndex = iNewIndex;
		}
	}
}

Actual Array
1)1
2)2
3)3
4)4
5)5


After Rotation
1)3
2)4
3)5
4)1
5)2

Sorry mistake while typing answer, answer should be [4,5,6,7,0,1,2].

Just add all elements in queue once. Second step is to do deque and queue the same element n times third step is to just de queue all elements and put them back on array

private static void Main(string[] args)
        {
            int[] input = { 5, 6, 7, 4, 0, 1, 2 };
            int direction = -4;

            if (direction < 0)
            {
                input = reverse(input);
            }

            for (int i = 0; i < Math.Abs(direction); i++)
            {
                rotate(input);
            }

            if (direction < 0)
            {
                reverse(input);
            }
        }

        private static int[] reverse(int[] input)
        {
            int i = -1;
            int j = input.Length;
            int tmp = 0;
            while (i++<j--)
            {
                tmp = input[i];
                input[i] = input[j];
                input[j] = tmp;
            }

            return input;
        }

        private static void rotate(int[] input)
        {
            if (input == null || input.Length == 0 || input.Length == 1)
            {
                return;
            }

            int i = input.Length - 1;
            int tmp = input[i];
            while (i > 0)
            {
                input[i] = input[i - 1];
                i--;
            }

            input[i] = tmp;
        }

Solution in Javascript

rotate = function(n) {
    return this.slice(n, this.length).concat(this.slice(0, n));
}

#include<iostream>
using namespace std;
int main(){
int ar[1000],length,i,rightshift,temp;
cin>>length>>rightshift;
for(i=0;i<length;i++)
cin>>ar[i];
rightshift%=length;
for(i=0;i<length/2;i++){
temp=ar[i];
ar[i]=ar[(i+rightshift)%length];
ar[(i+rightshift)%length]=temp;
}
for(i=0;i<length;i++)
cout<<ar[i]<<" ";
return 0;
}

void rrot(int a[],int size,int n)
{
int i,j,temp;
n%=size;
for(i=0;i<n;i++)
{
temp=a[size-1];
for(j=size-1;j>0;j--)
{
a[j]=a[j-1];
}
a[j]=temp;
}
}

public class Cup {
public static void main(String[] args) {

int []arrayIn={0,1,3,4,5,6,7};
int []arrayOut;
int n=4;

arrayOut=new Cup().reverseNum(arrayIn,n);

for(int i=0;i<arrayOut.length;i++){
System.out.println(arrayOut[i]);
}
}

public int[]reverseNum(int []arrayIn,int n){
int len=arrayIn.length;
int []arrayOut=new int[len];

for(int i=n,j=0;i<len;i++,j++){
arrayOut[j]=arrayIn[i];
}
arrayOut[n-1]=arrayIn[n-1];

for(int i=0,j=n;i<n-1;i++,j++){
arrayOut[j]=arrayIn[i];
}
return arrayOut;
}
}

int main(int argc, char** argv) {

int mat[7]={0,1,2,4,5,6,7};
int len=7;
int n=4;
int nindex=3;

for(int i=0;i<len;i++) cout<< mat[i]<<",";

cout << endl;
for(int i=0;i<nindex;i++)
{
mat[i]= mat[nindex+1+i]+mat[i];
mat[nindex+i+1]= mat[i]- mat[nindex+i+1];
mat[i]= mat[i]-mat[nindex+i+1];


}

for(int i=0;i<len;i++) cout<< mat[i]<<",";

return 0;
}

public class ArrayRotation
{
	public static void main(String[] args){
		
		int[] array = new int[] {1,2,3,4,5,6,7,8,9,10};
		
		System.out.println("*********************Right Rotation*********************");
		System.out.println("");
		printRightRotatedArray(array,2);
		System.out.println("*********************Left Rotation*********************");
		System.out.println("");		
		printLeftRotatedArray(array,2);
	}
	
	public static void printRightRotatedArray(int[] array, int rotation){
			int rotatedIndex = 0;
			int n = array.length;
		for(int i = 0; i < array.length; i++) {
			rotatedIndex = (i + rotation)%n;
			System.out.println(array[rotatedIndex]);
		}
	}
	public static void printLeftRotatedArray(int[] array, int rotation){
			int rotatedIndex = 0;
			int n = array.length;
		for(int i = 0; i < array.length; i++) {
			rotatedIndex = (i + (n - (rotation % n)))%n;
		/*	if(rotatedIndex >= array.length){
			
				rotatedIndex = rotatedIndex % array.length;
			} */
			System.out.println(array[rotatedIndex]);
		}
	}
}

int main(int argc, char **argv)
{
    std::cout << "Hello World" << std::endl;
	
	int n, a[50], rot, i;
	std::cout<< "Enter size of array \n";
	std::cin >> n;
	for (i = 0; i<n; i++)
	{
		std::cin >>a[i];
	}
	std::cout<<"Enter rotation number\n";
	std::cin>>rot;
	
	if (rot>n) return 0;
	
	if (rot == n) 
	//print org arr;
	{
		std::cout<<"\n";
		for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
	}
	for(i=0; i<(n-rot);i++)
	{
		//swap a[i] and a[i+rot]
		int temp = a[i];
		a[i]= a[i+rot];
		a[i+rot] = temp;
	}
	while(rot!=0)
	{
		//swap a[i] and a[i+rot]
		rot--;
		int temp = a[i];
		a[i]= a[n-1];
		a[n-1] = temp;
		i++;
		
	}
	//print
	std::cout<<"\n";
	for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
    return 0;
}

#include <iostream>


/* rotate an array by x
 * eg A[] = {1 2 3 4 5 6 7 8}
 * x=5
 * o/p A[] = {6 7 8 1 2 3 4 5}
 * O(n) = n*/
int main(int argc, char **argv)
{
    std::cout << "Hello World" << std::endl;
	
	int n, a[50], rot, i;
	std::cout<< "Enter size of array \n";
	std::cin >> n;
	for (i = 0; i<n; i++)
	{
		std::cin >>a[i];
	}
	std::cout<<"Enter rotation number\n";
	std::cin>>rot;
	
	if (rot>n) return 0;
	
	if (rot == n) 
	//print org arr;
	{
		std::cout<<"\n";
		for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
	}
	for(i=0; i<(n-rot);i++)
	{
		//swap a[i] and a[i+rot]
		int temp = a[i];
		a[i]= a[i+rot];
		a[i+rot] = temp;
	}
	while(rot!=0)
	{
		//swap a[i] and a[i+rot]
		rot--;
		int temp = a[i];
		a[i]= a[n-1];
		a[n-1] = temp;
		i++;
		
	}
	//print
	std::cout<<"\n";
	for (i=0;i<n;i++)
		std::cout<<a[i]<<"  ";
    return 0;
}

import java.util.*;
import java.lang.Math;

public class RotateArray{

    public static void main(String[] args){
	
		int[] ar = new int[]{0, 1,2,4,5,6,7};
		int rotation = 4;
		System.out.println(Arrays.toString(ar));
		rotateBy(ar, rotation);
		System.out.println("Rotate Right by " + rotation + " : " + Arrays.toString(ar));
		rotateBy(ar, -1*rotation);
		System.out.println("Rotate Left by " + rotation + " : " + Arrays.toString(ar));
    }

    public static void rotateBy(int[] array, int n){

        int numberOfRotation = n % array.length;
	if ( numberOfRotation > 0 ){
            for( int i = 0 ; i < numberOfRotation ; i++){
                rotateRightByOne(array);
            }
        } else {
	    for( int i = 0 ; i < Math.abs(numberOfRotation); i++){
		rotateLeftByOne(array);
	    }
	}
    }

    private static void rotateRightByOne(int[] array){
        int first = array[0];
        for ( int i = 0; i < (array.length - 1) ; i++){
            array[i] = array[i+1];
        }
        array[array.length - 1] = first;
    }

    private static void rotateLeftByOne(int[] array){
        int last = array[array.length - 1];
        for ( int i = array.length - 1; i > 0 ; i--){
            array[i] = array[i-1];
        }
        array[0] = last;
    }
}

###Python Code
mylist=[0,1,2,4,5,6,7]
len=len(mylist)
N=4
for i in range(len-N):  ##using len-N for reverse Rotate.Use N for Normal Rotate..
    mylist.append(" ")
    mylist[len]=mylist[0]
    del mylist[0]
print mylist

public int[] rotateArray(int[] arr,int n) {
        int prev;
        int next;

        for(int i = 0; i < arr.length; i++){
            if(n == arr[i]){
                n = i;
                break;
            }
        }

        for(int i = 0; i < n; i++ ){
                prev = arr[i];
                next = arr[n + 1 + i];
                arr[i] = next;
                arr[n + 1 + i] = prev;
        }

        return arr;
    }

Ruby implementation. Running time: O(nk). Space overhead: O(1).

def rotate(array, n)
  return [] if array.nil?
  return array if n <= 0 || array.length==0 || n % array.length == 0
  
  store_index=array.length-1
  
  (0...n).to_a.reverse.each do |element_index|
    for iter in (element_index...store_index)
      swap(array, iter,iter+1)
    end
    
    store_index -= 1
  end
  
  array
end

def swap(array, first_index, second_index)
  array[first_index]=array[first_index]^array[second_index]
  array[second_index]=array[first_index]^array[second_index]
  array[first_index]=array[second_index]^array[first_index]
  array
end

C Implementation
O(n) time complexity.
Number of iterations = n -1

#include <stdio.h>

int main(int argc, char **argv) {
    int k = 0, x = 0;
    int a[] = {-5,-4,-1,0,1,2,30,43,52,68,700,800,9999};
    int N = 0, R = 57; /*R = No of rotations*/
    int temp = 0, temp2  = 0, start = 0, iter = 0;

    x = 0;
    temp2 = a[x];

    N = sizeof(a) / sizeof(a[0]);
    for ( k = 0; k < N - 1; k++) {
        x = x + R;
        while ( x >= N ) {
            x = x - N;
        }
        temp = a[x];
        a[x] = temp2;
        temp2 = temp;
        if ( x == start ) {
            start = start + 1;
            x = x + 1;
            temp2 = a[x];
        }
        iter++;
    }
    a[start] = temp2;
    for ( k=0; k<N; k++) {
        printf(" %d", a[k]);
    }
    printf("\n");
    printf("Done in %d iteration\n", iter);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
void rotate(vector<int> & V, int N) {
	int n=V.size();
	int index=0;
	int val_old=V[index];
	int val_new;
	for(int i=0;i<n;i++) {
		val_new=V[(index+N)%n];
		V[(index+N)%n]=val_old;
		val_old=val_new;
		index=(index+N)%n;
	}
}
int main() {
	vector<int> V={0,1,2,4,5,6,7};
	rotate(V,4);
	for(int x:V)
		cout<<x;
}

O(n) time complexity, O(1) memory

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void rotate(vector<int> & V, int N) {
	int n=V.size();
	int gcd=__gcd(N,n);
	for(int i=0;i<gcd;i++) {
		int index=i;
		int val_old=V[index];
		int val_new;
		for(int j=0;j<n/gcd;j++) {
			val_new=V[(index+N)%n];
			V[(index+N)%n]=val_old;
			val_old=val_new;
			index=(index+N)%n;
		}
	}
}
int main() {
	vector<int> V={0,1,2,4,5,6,7};
	rotate(V,4);
	for(int x:V)
		cout<<x;
}

Not sure if this is right (pseudo code):

int N; //Given N value
int ip_array[]; //input array
int output_array[] = new int[ip_array.size]; // 

for(int i=0;i<ip_array.size;i++){
	output_array[(i+N)%ip_array.size] = ip_array[i];
}

Do nothing, just the way to read the elements as they are in the rotated array as newArray[i] = originalArray [(i-1+N) mod L] where L is the length of the (original) array. In case of rotating N1, N2, ..., Nk times, then aaply the same formula with N = (N1 + N2 + ... + Nk) mod L.

namespace consoleApp
{
class Program
{

static void Main(string[] args)
{
int[] array = new int[] {0,1,2,3,4,5,6,7,8 };
Console.WriteLine("please enter number : ");
int input = Convert.ToInt32(Console.ReadLine());
int number = 0 ;

for (int k = 0; k < input; k++ )
{
number = array[0];
for (int i = 1, j = 0; i < array.Length; i++, j++)
{

array[j] = array[i];

}
array[array.Length - 1] = number;
}
Console.WriteLine("Here is rotate : ");
for (int i = 0; i < array.Length; i++ )
{
Console.Write("{0}",array[i]);
}
Console.ReadKey();
}
}
}

namespace consoleApp{
class Program{
static void Main(string[] args){
int[] array = new int[] {0,1,2,3,4,5,6,7,8 };
Console.WriteLine("please enter number : ");
int input = Convert.ToInt32(Console.ReadLine());
int number = 0 ;
for (int k = 0; k < input; k++ ){
number = array[0];
for (int i = 1, j = 0; i < array.Length; i++, j++)
{ array[j] = array[i];}
array[array.Length - 1] = number; }
Console.WriteLine("Here is rotate : ");
for (int i = 0; i < array.Length; i++ )
{Console.Write("{0}",array[i]); }
Console.ReadKey();}}}

public static void Rotate(int[] inp, int rotate)
    {
        if(null == inp || inp.Length == 0)
            return;
        int len = inp.Length;
        int si=0;
        int hop = rotate % len;
        int temp1 = inp[si];
        int count = 0;
        while(count < len)
        {
            si = si + hop;
            if( si >= len)
                si = si - len;
            int temp2 = inp[si];
            inp[si] = temp1;
            temp1 = temp2;
           
            count++;
        }
        for(int index = 0; index< len;index++)
            Console.WriteLine(inp[index]);
    }