CareerCup

void reverse(int A[], int start, int end)
{
	while(start < end)
		swap(A[start++], A[end--]);
}

//shift A[0…sz-1] by n (n>0)
void shiftArray(int A[], int sz, int n)
{
	n = n%sz;
	reverse(A, 0, sz-1);
	reverse(A, 0, n-1);
	reverse(A, n, sz-1);
	return;
}

public static void circularShift(int[] inputArray, int shiftSize) {
        if (inputArray.length <= 1) {
            System.out.println("Array must have more than one integer.");

        } else {
            System.out.println("Before shift:--");
            for (int temp : inputArray) {
                System.out.println(temp);
            }
            int i = 0;
            int[] outputArray = new int[inputArray.length];
            while (i < inputArray.length) {
                int k = (shiftSize + i) % inputArray.length;
                outputArray[k] = inputArray[i];
                i++;
            }
            System.out.println("After shift:--");
            for (int temp : outputArray) {
                System.out.println(temp);
            }
        }
    }
}

C++ implementation with O(n) time and O(1) space using tail recursion.

#include <iostream>
#include <iterator>

static void rotate_right(int arr[], size_t len, int n)
{
	n = n % len;
	if (n == 0)
		return;

	for (size_t i = len - n, j = 0; i < len; i++, j++) {
		std::swap(arr[i], arr[j]);
	}

	return rotate_right(arr + n, len - n, n);
}

int main()
{
	int arr[] = {1, 2, 3, 4, 5, 6};
	rotate_right(arr, sizeof(arr)/sizeof(arr[0]), 2);
	std::copy(std::begin(arr), std::end(arr),
		std::ostream_iterator<int>(std::cout, " "));
	return 0;
}

int[] reverse(int[] A, int shifts)
	{
		int[] temp = new int[A.length * 2];
		System.arrayCopy(A, 0, temp, 0, A.length);
		System.arrayCopy(A, 0, temp, A.length, A.length);

		shifts = shifts % A.length;
		int[] result = new int[A.length];
		System.arrayCopy(temp, shifts - 1, result, 0, A.length);
	}

Explanation: temp array is A + A. And temp.length = 2*A.length.
e.g. A = [4,3,2,5] then temp = [4,3,2,5,4,3,2,5].
Now select the array between (including) (shifts - 1) and including shifts - 1 + A.length - 1.

The catch is to do it in place. No use of temporary array.

void rightShift(int[] array, int n) 
{
    for (int shift = 0; shift < n; shift++) 
    {
        int first = array[array.length - 1];
        System.arraycopy( array, 0, array, 1, array.length - 1 );
        array[0] = first;
    }
}

With a temp buffer of size n (or within a larger permanent buffer assigned to this task) we can:

N copies of last n elem. Of array into temp.
A.len-N copies of array's first elements from very front to very end.
Copy N elements from temp to start of array.

In total (a.len+N) writes.

for N is the size of the array and n < N/2 the following would work

for(int pass = 1; pass <= n ; pass++ )
			{				
				int carry = array[pass-1];
				
				for(int iter = pass - 1 ,count = 1; count <= N/n; count ++)
				{
					int tmp = array[(iter+n)%N];
					array[(iter+n)%N] = carry;
					carry = tmp;
					iter = (iter+n)%N;
				}

}

int size = array.Length;
            int i1 = 0;
            int i2 = size - shift;

            while (i1 < size-1)
            {
                swap(i1, i2, array);
                i1++;
                i2++;
                i2 = i2 == size ? size - shift : i2;
            }

public class CircularShiftArray {


	public static void main(String[] args) {
		int[] array = {2,5,1,8,10};
		shiftArray(array,2);
	}

	private static void shiftArray(int[] array, int n){
		int length = array.length;
		int i =0,temp = array[0],temp2 =0, count = 0;
		while(count!=length){
			int newIndex = (i+n)%length;
			temp2 = array[newIndex];
			array[newIndex] = temp;
			temp = temp2;
			count++;i = newIndex;
		}
	}

}

best sol would be if a swap gets minimized and in one shot the elements gets reolcation to right position.
for example : if we have array of size 6 and 4 shifts has to be done then
a[(i+s)%n] = a[i]
a[0] =a[4]
a[4] = a[2]
a[2] =a[0]
and so on

number of actual shift s = k % n

for( i=0 ; i < n/3 ; i++)
{
temp = a[i];
for(j=1; j < 4 ; j++)
{

next = ( i + j*s)%n
//swap the contents of a[next] and temp
temp1 = a[next]
a[next] = temp
temp = temp1
}
}

O(N) time, O(N) space... determine new position in array for bucket, move into temporary array, determine for next bucket etc...

int main()
{
	int arr[10] = {1,2,3,4,5,6,7,8,9,0};

	int *tempArr = new int[ sizeof(arr) / sizeof(int)];

	int n;

	cout << "Enter the number of shifts you would like to occur: ";
	cin >> n;

	for( int x = 0; x< (sizeof(arr) / sizeof(int)); x++)
	{
		int newPosition = (n + x ) % (sizeof(arr) / sizeof(int));
		tempArr[newPosition] = arr[x];
	}

	delete[] tempArr;
	tempArr = NULL;

}

The O(N) time and O(1) space looks optimal for small tables

void shiftArraySmall(int arr[], int aSize, int n)
{
 if (aSize == 0 || n == 0) return;
 int lastStart = 0;
 int lastIdx = 0;
 int saved = arr[0];
 for(int i = 0; i < aSize; ++i)
 {
  int nextIdx = (lastIdx + n) % aSize;
  if (nextIdx == lastStart)
  {
   arr[nextIdx] = saved;
   lastStart = lastIdx = (lastStart + 1);
   saved = arr[lastStart];
  }
  else
  {
   int temp = arr[nextIdx];
   arr[nextIdx] = saved;
   saved = temp;
   lastIdx = nextIdx;
  }
 }
}

but it's actually very bad for very large tables and relatively large n. Why? Because if n*sizeof(int) is larger than CPU cache this algo would generate only random memory accesses which can kill any algo. The modulo operation is expensive as well.

void shiftArrayLarge(int arr[], int aSize, int n)
{
 if (aSize == 0) return;
 n %= aSize; //make sure it's smaller than aSize
 if (n == 0) return;
 int tmpArr[n];
 memcpy(&tmpArr[0], &arr[aSize - n], n * sizeof(arr[0]));
 memmove(&arr[n], &arr[0], (aSize - n) * sizeof(arr[0])); //can implement better than that with reverse copy
 memcpy(&arr[0], &tmpArr[0], n * sizeof(arr[0]));
}

#include <iostream>
#include <stdio.h>

#define S 5

void show(int* w, int size)
{
printf("-------------\n");
for (int e = 0; e < size; ++e)
printf("%d \n", w[e]);
}

int main()
{
int tab[S] = { 1, 2, 3, 4, 5 };

int shift = 2;
int* w = new int[shift];
for (int k = 0; k < shift; ++k)
w[k] = tab[S - k - 1];

show(w, 2);

int tmp = S - shift - 1;
int dek = S - 1;
for (int z = tmp; z >= 0; --z)
tab[dek--] = tab[z];

int k = 0;
for (int e = shift - 1; e >= 0; --e)
tab[k++] = w[e];

show(tab, 5);

system("pause");
return 0;
}

#include <iostream>
#include <stdio.h>

#define S 5

void show(int* w, int size)
{
	printf("-------------\n");
	for (int e = 0; e < size; ++e)
		printf("%d \n", w[e]);
}

int main()
{
	int tab[S] = { 1, 2, 3, 4, 5 };

	int shift = 2;
	int* w = new int[shift];
	for (int k = 0; k < shift; ++k)
		w[k] = tab[S - k - 1];

	show(w, 2);

	int tmp = S - shift - 1;
	int dek = S - 1;
	for (int z = tmp; z >= 0; --z)
		tab[dek--] = tab[z];

	int k = 0;
	for (int e = shift - 1; e >= 0; --e)
		tab[k++] = w[e];

	show(tab, 5);

	delete[] w;

	system("pause");
	return 0;
}

public static void shiftRight( int[] arr, int shift ){
		
		if( arr == null ){
			throw new IllegalArgumentException("NULL 'arr' parameter passed");
		}
		if( arr.length < 2 ){
			return;
		}
		
		if( shift % arr.length  == 0 ){
			return;
		}
		
		int index = 0;
		int prev = arr[0];
		
		do{			
			int newIndex  = (index+shift) % arr.length;
			int temp = arr[newIndex];
			
			arr[newIndex] = prev;
			prev = temp;
			index = newIndex;				
		}
		while(prev != arr[index]);
		
	}

How about this

run a while loop for length of array. shift first element to n after copying a[n]th element to a local variable(k).
Now k will be copied to n1=(n+n)%len.
Similarly copy the existing element of the array and put the shifted element.

public static void Shift(int[] array, int n)
        {
            if (array.Length <= 1 || n == 0)
            {
                return;
            }

            n = n % array.Length;

            int i = 0;
            int k;
            int lastItem, temp;
            lastItem = array[0];            

            while (true)
            {
                k = (i + n) % array.Length;
                temp = array[k];
                array[k] = lastItem;
                lastItem = temp;
                i = k;

                if (i == 0)
                {
                    break;
                }
            }
        }

#include<stdio.h>
#include<conio.h>
main()
{
	int i,n,temp,var;
	int a[]={1,2,3,4,5,6,7,8,9};
	printf("\nEnter the shifting no: ");
	scanf("%d",&n);	/*right shift the array by n*/
	for(;n;n--)
	{
		var=a[0];
		for(i=1;i<=9;i++)
		{
			temp=a[i%9];
			a[i%9]=var;
			var=temp;
		}
	}
	getch();
}

public static void main(String[] args) {
		int[] array = {2,5,1,8,10,12,4,15};
		shiftArray(array,3);
		MyUtilities.PrintArray(array);
	}

	public static void Reverse(int[] A,int first, int last) {
		while(first < last){
			MyUtilities.Swap(A, first, last);
			first++;last--;
		}
	}
	private static void shiftArray(int[] array, int n){
		if(n<array.length && n >0){
			Reverse(array,0,array.length-1);
			Reverse(array,0,n-1);
			Reverse(array,n,array.length-1);
		}
	}

def s(l,n):
	n%=len(l)
	a=len(l)-n
	b=a+n
	i,j=a-n,b-n
	if i<0:
		i=0
	if j<0:
		j=0
	while a>0:
		l[a:b],l[i:j]=l[i:j],l[a:b]
		i,j,a,b=i-n,j-n,a-n,b-n
		if i<0:
			i,j=0,a
	return l

c++

#include <memory.h>

static void shiftArray(int shift, int arr[], int length )
{
int *tmp = new int[length];
memcpy(tmp, arr + (length-shift), sizeof(int)*shift);
memcpy(arr + shift, arr, sizeof(int)*(length-shift));
memcpy(arr, tmp, sizeof(int)*shift);
}

int main(int argc, char* argv[])
{
int arr[] = {1,2,3,4,5,6,7,8,9};
shiftArray(3, arr, sizeof(arr)/sizeof(*arr));
return 0;
}

private static void CircularRightShiftForArrayOfIntegers(int[] inputArray, int shift)
{
int[] outputArray = new int[inputArray.Length];
int i = 0;

while (i != inputArray.Length)
{
if (i + shift == inputArray.Length)
{
shift = -i;
}

outputArray[i + shift] = inputArray[i];

i++;
}

Console.WriteLine(string.Join(" ", outputArray));
}

int[] outputArray = new int[inputArray.Length];
            int i = 0;

            while (i != inputArray.Length)
            {
                if (i + shift == inputArray.Length)
                {
                    shift = -i;                   
                }
                
                outputArray[i + shift] = inputArray[i];

                i++;
            }

            Console.WriteLine(string.Join(" ", outputArray));

public void circle(int n)
{

int j = -1;
int[] aInt = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] aInt1 = new int[aInt.Length];
for (int i = n; i < aInt.Length ; i = i + 1)
{
j++;
aInt1[j] = aInt[i];
}
for (int i = 0; i < n; i = i + 1)
{
aInt1[aInt.Length - n + i] = aInt[i];
}
}

public void circle(int n)
{

int j = -1;
int[] aInt = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] aInt1 = new int[aInt.Length];
for (int i = n; i < aInt.Length ; i = i + 1)
{
j++;
aInt1[j] = aInt[i];
}
for (int i = 0; i < n; i = i + 1)
{
aInt1[aInt.Length - n + i] = aInt[i];
}
}

How about this: jump with step n, e.g. starting from index 0, n, 2*n, .... and swap their values. Do that n times with starting points in n first elements. O(N) time, O(1) memory.

public class shiftn {
	public static void shiftRight(int[] A, int shift)
	{
		for (int i = 0; i<shift; i++)
		{
			int j = i;
			int temp = A[j%A.length];
			while (j< A.length + i)
			{
				int temp2 = A[(j+shift)%A.length];
				A[(j+shift)%A.length] = temp;
				j = j+shift;
				temp = temp2;
			}
			
			
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A = {1,2,3,4,5,6,7,8,9};
		System.out.println("before");
		for (int i = 0; i<A.length;i++)
		{
		System.out.println(A[i]);
		}
		shiftRight(A,3);
		System.out.println("after");
		for (int i = 0; i<A.length;i++)
		{
		System.out.println(A[i]);
		}
	}

}

public class CircShift {
    public static void main(String[] args){
    int[] array=new int[]{0,1,2,3,4} ;
    int[] newarray=new int[5];
    int shiftsize=2;

    for(int i=0;i<array.length;i++){

      newarray[(i+shiftsize)%array.length]= array[i];
    }

        for(int i=0;i<array.length;i++){

            System.out.print(newarray[i]);

        }
}
}

github.com/techpanja/interviewproblems/tree/master/src/arrays/circularshiftintarray

int count =0,i=0,prev=arr[0],newInd,temp;
while(count<n){
count++;
newInd = (i+shift)%n;
temp = arr[newInd];
arr[newInd] = prev;
prev = temp;
i = newInd;
}

InPlace

void circularshift(int A[], int N, int sh)
{
sh = sh% N;
int cur = N - sh - 1; // it needs to move in N-1 th position
int dest = N - 1;
int DatatoMove = A[cur];
int count = 0;
while(count<N)
{
int temp = A[dest];
A[dest] = DatatoMove;
DatatoMove = temp;
cur = dest;
dest = (cur + sh) % N;
count++;
}
}

Msft asking toughest questions on the weekends f2f int. I can see that.
Maybe we can use A* search for this? I know the one guy who always posting A* as answer will suggest for this heuristic of A*. The question is a little bit tougher for intwrview in the face of face. It might take one week think to produce code with quartic runtimes and spaces.