[Solved] this is a code for left rotation of an array….how to optimize it further as it’s giving TLE error

by


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 );
}

2

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