Solved

left shift of an array of integers.

Posted on 2004-10-03
22
644 Views
Last Modified: 2013-12-14
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
Comment
Question by:subbu569
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 7
  • 5
  • 3
  • +4
22 Comments
 
LVL 84

Accepted Solution

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

Expert Comment

by:str_ek
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 84

Expert Comment

by:ozo
ID: 12215313
memmove(&array[0],&array[k],(n-k)*sizeof(array[0]));
(the time complexity is the same.)
0
The Ultimate Checklist to Optimize Your Website

Websites are getting bigger and complicated by the day. Video, images, custom fonts are all great for showcasing your product/service. But the price to pay in terms of reduced page load times and ultimately, decreased sales, can lead to some difficult decisions about what to cut.

 
LVL 3

Expert Comment

by:str_ek
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 84

Expert Comment

by:ozo
ID: 12215547
the time complexity is linear in either case
0
 
LVL 3

Expert Comment

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

Expert Comment

by:PaulCaswell
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

by:IceColdas
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; ....
...............
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
 
LVL 16

Expert Comment

by:PaulCaswell
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.

Could question author confirm please?

Paul
0
 
LVL 3

Expert Comment

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

Expert Comment

by:farsight
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 84

Expert Comment

by:ozo
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

by:Ruskialt
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

by:str_ek
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 84

Expert Comment

by:ozo
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

by:str_ek
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

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

Expert Comment

by:raghuraman_suraj
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

by:PaulCaswell
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

Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
This article will inform Clients about common and important expectations from the freelancers (Experts) who are looking at your Gig.
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…
Progress

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question