PIYUSH SHEKHAR PIYUSH SHEKHAR - 3 months ago 7
C++ Question

this is a code for left rotation of an array....how to optimize it further as it's giving TLE error

#include <iostream>


using namespace std;


int main() {

int n,d,i=0,temp;
cin>>n>>d;
int a[1000000];
for(i=0;i<n;i++){
cin>>a[i];
}

while(d--){

temp=a[0];

for(i=1;i<n;i++){
a[i-1]=a[i];}
a[n-1]=temp;
}

for(i=0;i<n;i++){

cout<<a[i]<<" ";

}
return 0;
}


how to optimize it further as it's giving TLE error. the input file is very large obviously.

Answer

Some suggestions:

  1. Rotate by the full amount d in a single loop (note that the result is a different array b):

    for (i = 0; i < n; i++) {
        b[(i+n-d) % n]=a[i];
    }
    
  2. Don't touch the array at all but transform the index when accessing it, for example:

    cout << a[(i+n-d) % n] << " ";
    

The second version requires extra calculation to be done whenever accessing an array element but it should be faster if you don't need to access all array elements after each rotate operation.

  1. There is also a way to do the rotation in-place by using a helper function that reverses a range of the array. It's a bit odd but might be the best solution. For convenience I have used a std::vector instead of an array here:

    void ReverseVector( std::vector<int>& a, int from, int to ) {
        for (auto i = 0; i < (to - from) / 2; i++) {
            auto tmp = a[from + i];
            a[from + i] = a[to - i];
            a[to-i] = tmp;
        } 
    }
    
    void RotateVector( std::vector<int>& a, int distance ) {
        distance = (distance + a.size()) % a.size();
        ReverseVector( a, 0, a.size() - 1 );
        ReverseVector( a, 0, distance - 1 );
        ReverseVector( a, distance, a.size() - 1 );
    }