CareerCup

This is array rotation question.
wwwDOTgeeksforgeeks.org/array-rotation/

Here are the possible solutions:

Solution #1 (brute force)
1. temp = first element of array
2. Shift all the remaining array elements left by 1
3. last element of array = temp
4. Continue for n steps
Time complexity: O(n * k)

Solution #2 (with a temp array)
1. Copy the first n bits to a temp array.
2. Move the remaining arrayLength - n bits to front
3. Copy the temp array to the end
Space complexity: O(k), Time complexity: O(n)

Solution #3 (with reverse):
FrickinHamster solution - reverse the strings. But reversing a string takes O(n) and this will need 3 reverse. Good but not the best.

Solution #4 (most efficient solution and I think the interviewer is looking for this one)
Circular left shift the entire array with each element moved to right position at first iteration itself. This will utilize mod operation to compute next position. I could explain more, but the following link does a far better job. Time Complexity: O(k) Best case, O(n) average case

stackoverflow.com/questions/11893053/circular-left-shift-of-an-array-by-n-positions-in-java

PS: k = number of elements, n = array length

Here is my algorithm :
Consider you have an array which can be split into A( first N elements), B( remaining array)
1. Reverse the first n elements in the array.
2. Reverse the elements n+1 to end of the of the array.
3. Reverse the whole array once.

Eg : say you have an Array [1, 2, 3, 4, 5 ,6, 7,8,9,10]

say n = 3 meaning 3 elements have to copied to end of the array. expected output is [4,5,6,7,8,9,10,1,2,3]

1) we will have [3,2,1,4,5,6,7,8,9,10]
2) we will have [3,2,1,10,9,8,7,6,5,4]
3) we will have [4,5,6,7,8,9,10,1,2,3] => expected output

public class ReversefirstNuNUmbers {
	public static void main(String[] args) {
		int a[] = { 2, 12, 8, 6, 5, 1, 2, 10, 3, 2 };
		reverseArray(a,3);
		display(a);
		
	}

	public static void display(int a[]) {
		for (int a1 : a) {
			System.out.print(a1 + ",");
		}
	}

public static void reverseArray(int a[],int count)
{
	for (int i=0;i<count;i++) {
		
		int temp=a[i];
		a[i]=a[a.length-i-1];
		a[a.length-i-1]=temp;;
	}
}
}

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

main()
{
        int a[10] = {1,2,3,4,5,6,7,8,9,0},*ptr,i,j,n;

        ptr = malloc(10*sizeof(int));

        printf("enter how many no's wish to push\n");
        scanf("%d",&n);

        //copying last 10-n into ptr//

        for(i=n,j=0;i<10;i++,j++)
        {
                *(ptr+j) = a[i];
        }

        //copying first n into ptr //

        for(i=0,j=10-n;i<n;i++,j++)
        {
                *(ptr+j) = a[i];
        }

        for(i=0,j=0;i<10,j<10;i++,j++)
        {
                a[i] = *(ptr+j);
        }


        for(i=0;i<10;i++)
        {
                printf("%d ",a[i]);
        }

        printf("\n");
        free(ptr);
}

public static void moveToEnd(int[] a, int n){
		int[] temp = new int[a.length];
		for(int i = 0; i < a.length; i++){
			temp[i] = a[i];
		}
		for(int i = 0; i < a.length - n; i++){
			a[i] = temp[i + n];
		}
		
		int j = 0;
		for(int i = a.length - n; i < a.length; i++){
			a[i] = temp[j];
			j++;
		}
	}

if n element has does not have to maintain the same order, this might work.

void move(int arr[], int n)
{
    // if n is less than or equal to 5 we swap first n elem with last n elements
    // if n is greater than 5, we swap first 10 - n elements with the last (10-n) elements
    
    if (n >= 10 || n < 0) return;

    int j = 10 - 1;
    int numSwaps = n <= 5 ? n : 10 - n;

    for (int i = 0; i < numSwaps; i++, j--)
    {
        swap(&arr[i], &arr[j]);
    }
}

public static void ReverseArray()
{
int[] arr= new int[] {1,2,3,4,5,6,7,8,9,10};
int[] Temparr= new int[10];
int n;
Console.WriteLine("Enter no of element to be reverse <10");
n = Convert.ToInt16(Console.ReadLine());

for (int i = 0; i < arr.Length; i++)
{
if ((i + 1) <= n)
{
Temparr[i] = arr[i];
}
else
{
break;
}
}
Console.WriteLine("element is going to reverse");
foreach (var item in Temparr)
{
Console.Write(item +",");
}
//shifting the reamning array1
for (int i = n; i < arr.Length; i++)
{
arr[i - n] = arr[i];

}
Console.WriteLine("After shifting");
foreach (var item in arr)
{
Console.Write(item + ",");
}

//shifting the reamning array2
int loc= arr.Length -n;

for (int i = 0; i < n; i++)
{
arr[loc]=Temparr[i];
loc++;
}

Console.WriteLine("After All");
foreach (var item in arr)
{
Console.Write(item + ",");
}

}

I am not going to swift the array element but I have solution to get the expected output

New_index=Index+(10-num_of_swift) % 10

#include <stdio.h>

int main(void) {
	int array [] = { 1, 2, 3, 4, 5, 6, 7, 8, 9};
	
	int prev, next;
	
	int k = sizeof (array)/sizeof (array[0]);
	int n = 4;
	
	int i = 0;
	int j = 0;
	
	prev = array [0];
	
	for (;;)
	{
		j = (i + n) % k;
		
		next = array [j];
		array [j] = prev;
		
		prev = next;
		i = j;
		
		if (j == 0)
			break;
	}
	
	for (i = 0; i < k; i++)
	 	printf ("%d, ", array [i]);
	
	return 0;
}

private static void moveToRight(int [] array, int n){

for( int i =0 ; i< array.length - n; i++){
int tmp = array[i];
array[i] = array[i + n ];
array[i+n] = tmp;
}

}

// Left shift the array in O(n) with O(1) space.

	public static void leftShift(int[] array, int n) {
		int temp;
		int len = array.length;
		for (int i = 0; i < n; i++) {
			temp = array[len - n + i];
			array[len - n + i] = array[i];
			array[i] = array[n + i];
			array[n + i] = temp;
		}
	}

static int[] moveNelements(int[] array, int n) {
		
		
		for (int i = 0; i < n; i++) {
			
			int temp = array[n];
			array[n++] = array[i];
			array[i] = temp;
			if (n == array.length) break;
		}
		return array;

}

Simple swappings

The suggested method takes O(n) time for reversing the elements..

In java, we can use subList method of ArrayList class. I guess it takes constant time...

List<Integer> list1 = list.subList(0, 4);
list = list.subList(4, 9);
list.addAll(list1);

Can anyone confirm ?

Use LinkedList<T>
p://msdn.microsoft.com/ru-ru/library/he2s3bh7(v=vs.110).aspx

Array rotation is inefficient as its complexity is O(n*n). I suggest you hould try place swaping with n and 10-n. In that case complexity is only O(n)