Solved

left shift of an array of integers.

Posted on 2004-10-03
22
627 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
  • 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
 
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

How to remove superseded packages in windows w60 or w61 installation media (.wim) or online system to prevent unnecessary space. w60 means Windows Vista or Windows Server 2008. w61 means Windows 7 or Windows Server 2008 R2. There are various …
Entering a date in Microsoft Access can be tricky. A typo can cause month and day to be shuffled, entering the day only causes an error, as does entering, say, day 31 in June. This article shows how an inputmask supported by code can help the user a…
Learn several ways to interact with files and get file information from the bash shell. ls lists the contents of a directory: Using the -a flag displays hidden files: Using the -l flag formats the output in a long list: The file command gives us mor…
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…

746 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

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now