• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 669
  • Last Modified:

left shift of an array of integers.

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
subbu569
Asked:
subbu569
  • 7
  • 5
  • 3
  • +4
1 Solution
 
ozoCommented:
for(i=k;i<n;i++){ array[i-k]=array[i]; }
0
 
str_ekCommented:
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
 
ozoCommented:
memmove(&array[0],&array[k],(n-k)*sizeof(array[0]));
(the time complexity is the same.)
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
str_ekCommented:
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
 
ozoCommented:
the time complexity is linear in either case
0
 
str_ekCommented:
well there is some seroius difference between O(n) and O(2n) complexity
0
 
PaulCaswellCommented:
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
 
IceColdasCommented:
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; ....
...............
after reading or computing k
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
 
PaulCaswellCommented:
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.

Could question author confirm please?

Paul
0
 
str_ekCommented:
it wont shift, it'll trunc the arary ! that's preaty major differnece !!!
0
 
farsightCommented:
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
 
ozoCommented:
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
 
RuskialtCommented:
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
 
str_ekCommented:
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
 
ozoCommented:
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
 
str_ekCommented:
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
 
str_ekCommented:
your 1. post implements it's idea perfectly
( for(i=k;i<n;i++) array[i-k]=array[i];)
0
 
raghuraman_surajCommented:
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
 
PaulCaswellCommented:
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 7
  • 5
  • 3
  • +4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now