Solved

# left shift of an array of integers.

Posted on 2004-10-03
Medium Priority
684 Views
There is an array of n integers and a variable k.we have to left shift the array k times with best possible time complexity.I want a c language program for this problem.
0
Question by:subbu569
• 7
• 5
• 3
• +4

LVL 85

Accepted Solution

ozo earned 2000 total points
ID: 12215118
for(i=k;i<n;i++){ array[i-k]=array[i]; }
0

LVL 3

Expert Comment

ID: 12215211
well there is a major difference between shift and rot!
if you wanna shift then simply memmove rocks

memmove( where, what, howmuch ); <string.h>
wnen where is what+offste, and howmuch is length -offset youll get a shift (left as i suppose)

and for rot i'll simply buffer the overlaping area, so it makes 2 memmoves an alloc and free to complete
0

LVL 85

Expert Comment

ID: 12215313
memmove(&array[0],&array[k],(n-k)*sizeof(array[0]));
(the time complexity is the same.)
0

LVL 3

Expert Comment

ID: 12215472
the difference is in fact memmove wil use maximum possible data chunk size for copying , and rewriting array cell by cell regardles the processor capabilities

ie. 32 bit uP and 16 (short) integer array would:
memmove

((int)(length-offset)/(int)2) 32 bit move instrucitons
and rest (1 or 0 ) in 16 bit move

while rewriteing array would take a constant length-offset 16 move...

and for a 32bit uP 16 and 32 moves are executed with equal cycles (so time as well) cost

that's why moving is almost always (sometimes you just need to process the data as well and processing while rewiting saves some time) smater move than direct rewriting
0

LVL 85

Expert Comment

ID: 12215547
the time complexity is linear in either case
0

LVL 3

Expert Comment

ID: 12216093
well there is some seroius difference between O(n) and O(2n) complexity
0

LVL 16

Expert Comment

ID: 12217236
If you want to shift 'k' BITS then you'd be better to walk two pointers down the array like ozo said but add some shifting in.

If thats the case, let us know.

Paul
0

LVL 3

Expert Comment

ID: 12218330
faster way (though this would be a trick and you must do it in c++ or visual c++) is this  :
1) if you create the array after reading k (the number of shifts), then it`s simple, just allocate memory to the array, so it will be the number of elements + number of the shift  (in this case is  k ) , and start to fill the array from position k.

c++ example (notice that this is the old c++, with int on 16 bits)
#include <alloc.h>
.....
int k = 30; //any other value or read it from keyboard
int * x;
x = (int *)malloc(100+k); //100 =  how many integers holds your array;
//fill x with numbers starting from half of the size, like : x[k] = 3; x[k+1] = 9; etc..
//then x[0] will be first element  of the shifted array
2) if you create it before reading k, then allocate to the array a number of elements which you know it cant be bigger than k+(actual number of elements);
for example :
int maxK = 500;
int * x;
x = (int *)malloc(100+maxK);
//fill x with numbers starting from maxK; x[maxK] = 3313; x[maxK+1] = 5412; ....
...............
int * x1 = x +maxK - k;
//after this, x1[0] will be the first element of the shifted array, and x1[k] will be the first element of the old array;

That sounds too complicated ? :D
0

LVL 16

Expert Comment

ID: 12218423
If you want byte shifts then:

byte * shifted = &a[k];

which, if I'm not mistaken, would be O(0) or O(1) depending on the deeper meaning of 'O'. ;)

However, due to the above truism, I'm willing to bet we are talking bit shifts which would be a much more entertaining discussion.

Paul
0

LVL 3

Expert Comment

ID: 12218863
it wont shift, it'll trunc the arary ! that's preaty major differnece !!!
0

LVL 12

Expert Comment

ID: 12222043
Yes, you could actually move the data.
(If this is an academic problem (homework), that's probably what they're expecting.)

But you could also make a class that is a view into the original array.  Then, just manipulate the indexes, and leave the original data in the original array.  You'll be "virtually" shifting the array.

This is an object-oriented solution, so you'd need to customize it to plain (non-object) C.

[rough pseudo-code]
class ArrayView {
private int offset;
public int[] baseArray;
public int Item(int index) {
return baseArray.Item(getIndex(index));
}
public int getIndex(int index) {
int result;
result = index + offset;
if (result < 0) {
result += baseArray.length();
}
}
public void shiftLeft(int k) {
offset -= k;
}
public void shiftRight(int k) {
offset += k;
}
}

// sample use
ArrayView myArray;
myArray.baseArray = originalArray;
myArray.shiftLeft(5);
myArray.shiftRight(3);
int i;
for (i=0; i++; i< myArray.baseArray.length()) {
DoSomething(myArray.Item(i));
}

I'm a little rusty on pointers and arrays in C, but the idea here is that you can initialize the baseArray by just giving the new class a pointer to the original array.  shiftLeft and shiftRight then only takes as much time as an addition or subtraction (and a call), no matter how far you shift it.  Indexing each element will take a little bit longer, though.

You can handle shift or rotation in getIndex().  I did rotation.   If shiftLeft(), followed by shiftRight() would result in 0 in baseArray(0), then you'd have to keep track of the maximum number of items shifted off (at each end) and have Item() return 0 if the outside those bounds.

That's a lot faster than actually moving data around.
0

LVL 85

Expert Comment

ID: 12222275
O(n) = O(2n)
Or if you want a new array pointer that's a left shift of the old array pointer,
shift = &array[k];
is O(1)
0

LVL 2

Expert Comment

ID: 12224461
Instead of actually moving the data why not move the index and use % operation? Depend if access if a performance issue. If I want value t at index i for the array shiftet k times

int* pArray = new int[n];
int t = pArray[(k+i)%n];
0

LVL 3

Expert Comment

ID: 12224617
it wont shift, it'll trunc the arary ! that's preaty major differnece !!!

ozo, and Ruskialt
shift operation must return register/word of the same saze
0

LVL 85

Expert Comment

ID: 12224660
You want a C function that takes an integer array and returns a register/word?
What relation should this register/word have to the array?
Also, could you clarify what you mean by "shift"?
0

LVL 3

Expert Comment

ID: 12224801
seen that / between register/word... it meant the subject is somthing like register and like word...

if information entity is array entry then a finite set of such entrys is word of that entities (just like a i.e. bit entity and 32-bit word set)...

shift operation is an word ( information entity set) manipulation, shift operation translates (just like in 1-dimmesional goemetry) the word. it drops (ignores\ truncates) entities that after translation resides beyond word , it's state in places where no infomration were written is undefinied, or user defined (ie. most bit shofts are used also for extra fast 2^n multipcations, so it's user defined state is 0 !)
0

LVL 3

Expert Comment

ID: 12224815
your 1. post implements it's idea perfectly
( for(i=k;i<n;i++) array[i-k]=array[i];)
0

Expert Comment

ID: 12265466
The Best way to left shift the array if ur not goin to add any entries to it after that is to move the array pointer to that location if u want to move k locations to the left then just do
array=array+k;
thats the fastest method to do it.
But can cause memory leaks if u forget to delete the portion from array to array+k.
0

LVL 16

Expert Comment

ID: 12470861
I'd suggest 'Accept ozo'. He covered each of the possible alternatives completely and concisely. There were some other valuable assists.

Paul
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.