Shifting arrays k positions without using additional memory

[Veneficvs]

Hello everyone. I am having hard times in dealing with this problem which I've been given. It simply asks me to shift an array K positions without using additional memory. I cannot ask them what they mean by that. No memory, like... not even using a temporary variable for the loop?!

Here is an example:
1 2 3 4 5 6 7 8 shifted 3 times to the right gives:
4 5 6 7 8 1 2 3

Of course, the array is not sorted necesarray, that was just an example.

#include <iostream>

using namespace std;

void shiftArray(int numbers[], int sizeofArray, int k)
{
	int index;
	for(index = 0; index < sizeofArray;  index++)
	{
		if(index >= sizeofArray - k)
		{
			numbers[index] = numbers[index % (sizeofArray - index)];
		}
		else
		{
			numbers[index] = numbers[index + k];
		}
	}
}

int main(int argc,char* argv) 
{
	int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8};
	int k = 3;
	int sizeofArray = 8;
	shiftArray(numbers, sizeofArray, k);
	int i;
	for(i = 0; i < sizeofArray; i++)
	{
		cout << numbers[i] << " ";
	}
	cout << endl;

	return 0;
}

This is my code so far. I know I used a temporary variable for the size, but that was because I cannot do it with sizeof...

Also, the problem is that after updating the first sizeofArray - k numbers, the last k numbers will be updated with the replaced values and not with the original ones... can someone please tell me how should I correct it? Or at least give me another way of looking at the problem? Thanks for your time.

[griswolf]

Well, in the first place this is a "rotate" function, not a "shift", but I'll assume you really want "rotate"

You are stepping on your data: What happens to the number that was at index in lines 12 and 16? When it is time to shift it, where is the original data?

I would consider writing a function:

void rotateLeftOne(Type array[], length) {
  Type tempdata = array[0]
  for (int i = 0; i < length-1; ++i) {
    array[i] = array[i+1];
  }
  array[length-1] = tempdata;
}

(something like that) Then, of course, you just call it several times.

This does use two local variables (int i and whatever type tempdata is). Perhaps the point of the exercise is to make you think about such things. Note that the suggested plan is not very efficient in time, but very small space overhead. Can you trade time for space? (of course you can: just write into a whole new array, eh?)

I did NOT check for syntax or fencepost problems...

[Veneficvs]

Thank you very much, sir! But how do I rotate to the right k positions, please? From what I see there, it rotates it to the left one time. Thanks.

[WaltP]

Thank you very much, sir! But how do I rotate to the right k positions, please? From what I see there, it rotates it to the left one time. Thanks.

So do it k-1 more times -- use a loop.

[vijayan121]

If the number of elements is large and the size of each element is small (eg. an array of int), the well known reverse three times technique seems to be the most efficient.

void reverse( int a[], std::size_t N )
{
    for( std::size_t i = 0 ; i < N/2 ; ++i ) std::swap( a[i], a[N-i-1] ) ;
}

void rotate_left( int a[], std::size_t N, int BY )
{
    BY %= N ;
    reverse( a, BY ) ;
    reverse( a+BY, N-BY ) ;
    reverse( a, N ) ;
}

Otherwise, something similar to a typical std::rotate() implementation.
http://cplusplus.com/reference/algorithm/rotate/