CODEWITHSUNDEEP
c++arraysdata-structurescompile-time
Dis Guise
Dis Guise

Reputation: 61

rotating the array anti-clockwise, run time issues

In the question, I had to rotate the data in an array anti-clockwise by d numbers. But it is taking more time to run than required to qualify for submission. Can anyone help me with how to optimize the code to run it in less time?Thanks!

here's the code:

int main() {
int test_cases,size,d;
std::cin>>test_cases;
while(test_cases!=0){
std::cin>>size>>d;
int ar[size];
for(int i=0;i<size;i++){
    std::cin>>ar[i];
}
while(d!=0){
    int x = ar[0];
    for(int i=1;i<size;i++){
        ar[i-1]=ar[i];
    }
    ar[size-1]=x;
    d--;
}
for(int i=0;i<size;i++){
    std::cout<<ar[i]<<" ";
}
test_cases--;
cout<<endl;
}}

Upvotes: 2

Views: 467

Answers (3)

Bob__
Bob__

Reputation: 12759

While the problem is about a rotation to the left (anti-clockwise as you say), we can always reformulate it as a rotation by a given (positive) offset to the right.

For instance, given the following array (which should be a std::vector, in C++) of size n = 9

1 2 3 4 5 6 7 8 9

A rotation to the left of 3 places (d = 3, in OP's problem), is equivalent to a rotation to the right of 6 places (let's call this offset k, so that k = 6):

4 5 6 7 8 9 1 2 3

If you can use extra memory, the easiest way should be to copy the first n - k elements (or the last k elements) into a temporary buffer, move the remaining k ones at the beginning (or the first n - k at the end) and then copy back the elements from the buffer into the last positions (or, you know...).

    [1 2 3 4 5 6 7 8 9]      [     ]
     ^ ^ ^                               Copy the first elements
    [1 2 3 4 5 6 7 8 9]      [1 2 3]
           ^ ^ ^ ^ ^ ^                   Move to the beginning
    [4 5 6 7 8 9 7 8 9]      [1 2 3]
                              ^ ^ ^      Copy back
    [4 5 6 7 8 9 1 2 3]      [1 2 3]

If you can't and the assignment requires the array to be modified in place, a nice alternative to the Juggling algorithm showed in the other answers requires only three reverses:

    [1 2 3 4 5 6 7 8 9]
     ^ ^ ^                     Reverse the first n - k elements     
    [3 2 1 4 5 6 7 8 9]
           ^ ^ ^ ^ ^ ^         Reverse the last k elements  
    [3 2 1 9 8 7 6 5 4]
     ^ ^ ^ ^ ^ ^ ^ ^ ^         Reverse all
    [4 5 6 7 8 9 1 2 3]

If you are writing real code, you'd better use std::rotate.

Upvotes: 1

mfnx
mfnx

Reputation: 3018

You should move each element once as suggested in the comments. Figuring out an algorithm to do so is not that hard. However, why reinvent the wheel?

You can simply use std::rotate. I will assume anti-clockwise means to the left, and that an array starts at the left and ends at the right :).

std::vector<int> v {1,2,3};
size_t dist = 4; // rotate 4 to the left
std::rotate(v.begin(), v.begin() + dist % v.size(), v.end());

If you really insist on reinventing the wheel, I guess there are many possible algorithms. The example below starts at index idx = 0, and stores there the value at index idx_moved = idx + dist where dist is the rotation distance. We do then the same with idx = idx_moved, and repeat this N times, where N is the size of the array. I used std::vector here, but that doesn't change the algorithm. 

std::vector<int> v {1,2,3,4,5};
size_t dist = 3; // distance to move to the left

size_t idx = 0;
int tmp = v[0]; // store the initial value

for (size_t it = 0; it < v.size(); ++it)
{
    size_t idx_moved = (idx + dist) % v.size();
    v[idx] = v[idx_moved];
    idx = idx_moved;
}
v[dist * (v.size() -1 ) % v.size()] = tmp; // store the initial value back

Upvotes: 2

Kiseea
Kiseea

Reputation: 53

To make it faster you can use the A Juggling Algorithm, here is good explained how it works. The main principle is that you are not moving the elements one by one, but you are moving the elements within the equal sets.

Upvotes: 1

Related Questions