Shifting arrays K positions without using additional memory

This is a discussion on Shifting arrays K positions without using additional memory within the C++ Programming forums, part of the General Programming Boards category; I have been tasked with a program that shifts an array k position without additional memory. I don't know what ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    43

    Shifting arrays K positions without using additional memory

    I have been tasked with a program that shifts an array k position without additional memory. I don't know what kind of memory are they talking about, because I will obviously have to use one index value for the loop... Anyway, here is an example:
    shiftArray(numbers, k) for 1 2 3 4 5 6 7 8 and k = 3 should give: 4 5 6 7 8 1 2 3.

    The problem is simple, however, after constantly failing at minor things, I cannot think clear anymore. Here is my full code. The result for 1 2 3 4 5 6 7 8 is 5 2 3 4 5 6 7 8. I have discovered that the problem is in the if statement, but I cannot figure out why. I know the code is cluttered for the function, but that is only because I do not want to store the size into a variable, because of that memory condition...

    If you cannot find a way around the program, could you give me another suggestion if there is a more efficient way? Thank you very much.

    Cosmin

    Code:
    #include <iostream>
    
    using namespace std;
    
    void shiftArray(int numbers[], int k)
    {
    	int index;
    	for(index = 0; index < (int)(sizeof numbers)/(sizeof numbers[0]);  index++)
    	{
    		if(index >= numbers[(int)(sizeof numbers)/(sizeof numbers[0]) - k])
    		{
    			numbers[index] = numbers[index % k];
    		}
                                    else
                                    {
                                                    numbers[index] = numbers[index + k];
                                    }
    	}
    }
    
    int main(int argc,char* argv) 
    {
    	int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8};
    	int k = 4;
    	shiftArray(numbers, k);
    	int i;
    	for(i = 0; i < (int)(sizeof numbers)/(sizeof numbers[0]); i++)
    	{
    		cout << numbers[i] << " ";
    	}
    	cout << endl;
    
    	return 0;
    }
    Last edited by Veneficvs; 03-29-2011 at 06:06 PM. Reason: I forgot to add else

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    The shiftArray function cannot do sizeof(numbers). You need to pass the size of the array to the function:

    Code:
    void shiftArray(int numbers[], size_t array_size, int k)
    bit∙hub [bit-huhb] n. A source and destination for information.

  3. #3
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Does "no additional memory" mean that you can't even use a single temporary variable?
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    Hahaha... For showing only, you can do;
    Code:
    for(int i=k;i<lengthOfArray;i++)
    {
    cout<<numbers[i];
    }
    for(int j=0;j<k;j++)
    {
    cout<<numbers[j];
    }
    But that's only for display. I know you actually mean, shifting, i am thinking .............
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    I did it somehow. But the problem now is that the last k numbers are replaced with the first k variables whose original values have been replaced...

    Code:
    #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;
    }
    Also, isn't it another way to determine the size of an array on the fly so I do not use a storage variable?

  6. #6
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    I want to ask one thing, that you aren't allowed to use even a single variable except the specified ones?
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  7. #7
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    Quote Originally Posted by Mr.777 View Post
    I want to ask one thing, that you aren't allowed to use even a single variable except the specified ones?
    I suppose. But I have been thinking for more than two hours already and I have also asked an advice from an Informatics teacher and I have been told that it is impossible without having at least one variable and that is for the loop.

    So I accept the use of a single variable... I am afraid I have no choice.

    Mr. 777, is it possible without using one too? I would like your opinion concering the use of a variable, but I do not want to neglect the second approach as well.

  8. #8
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    I think you will have to use one temporary variable.
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  9. #9
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    I have managed to ask informations. Yes, I am allowed to use temporary variables! Pfew. Now could you please tell me what is wrong in my problem so the thread can be closed?

  10. #10
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    Now simple do;
    Code:
    int temp=0;
    for(int index=0;index<k;index++)
    {
    temp=numbers[k];
    numbers[k]++=numbers[index];
    numbers[index]=temp;
    }
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

  11. #11
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    Quote Originally Posted by Mr.777 View Post
    Now simple do;
    Code:
    int temp=0;
    for(int index=0;index<k;index++)
    {
    temp=numbers[k];
    numbers[k]++=numbers[index];
    numbers[index]=temp;
    }
    I think it should be numbers[k++], with the k between brackets. This code assign to the first k values the ones of the next k. However, the first three ones will be replaced after performing the code...

    I am way too confuse after so many nerves and failures... Here is the problem:

    I will be succesfully turning the first 5 numbers into the next three ones. So 1 becomes 4, 2 becomes 5, 3 becomes 6, 4 becomes 7, 5 becomes 8. But about the last three? How could I make them become 1 2 3 without using a second array to store these?

  12. #12
    Programming King Mr.777's Avatar
    Join Date
    Mar 2011
    Location
    Middle of NoWhere
    Posts
    320
    Yes my typing mistake. it will be numbers[k++]. Sorry.
    I don't care if someone doesn't like me, i was not put on earth to entertain everyone.

    No King, no Queen, I am the ACE of battle.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Memory Fragmentation with Dynamic FIFO Queue
    By fguy817817 in forum Linux Programming
    Replies: 17
    Last Post: 10-31-2009, 04:17 AM
  2. Assignment Operator, Memory and Scope
    By SevenThunders in forum C++ Programming
    Replies: 47
    Last Post: 03-31-2008, 06:22 AM
  3. Reallocating Memory
    By Booie2k1 in forum C Programming
    Replies: 3
    Last Post: 03-11-2008, 06:09 AM
  4. Help with a problem regarding dynamic memory and arrays
    By Michty in forum C++ Programming
    Replies: 5
    Last Post: 07-26-2006, 01:26 PM
  5. shifting arrays
    By ZeroG in forum C Programming
    Replies: 6
    Last Post: 06-16-2004, 10:13 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21