reduce the time complexity of below given code .The code working fine the problem is time complexity

Question

/*The first line will consist of one integer T denoting the number of test cases. For each test case:

The first line consists of two integers n and r, n being the number of elements in the array and r denotes the number of steps of rotation.
The next line consists of N space-separated integers, denoting the elements of the array a.

Constraints:

1<=t<=20

1<=n<=10^5

0<=k<=10^6

0<=a[i]<=10^6

Input

1

5 2

1 2 3 4 5 6

Output

4 5 1 2 3 */

// my code

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main(){
   
    int t,n,r;
    cin>>t;
    
    for (int i = 0; i < t; i++)
    {
        cin >> n >> r;                    // inputting number of element in array and number of rotation
        int a[n];
        for (int i = 0; i < n; i++)
        {
            cin>>a[i];                                           //taking input from user in array
        }
        n--;
        for (int i = 0; i < r; i++)
        {
            n++;
            for (int i = n; i >= 0; i--)
            {
                a[i]=a[i-1];
            }                                    // help me to improve this inner loop and add a little bit 
            a[0]=a[n];                           //of explanation for your logic and pls give answer in c++
            n--; 
        }
        for (int i = 0; i <= n; i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

I can't compile your code. Please read [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — Ted Lyngmo, Feb 25 '21 at 08:33
What is the code supposed to do? Have you enabled compiler optimisations? How fast is the code? How fast do you need it to be? — Alan Birtles, Feb 25 '21 at 08:42
The problem is probably that you use nested loops for the rotation. You are rotating `r` times in a loop instead of rotating `r` steps at once. This should be something like `a[i]=a[i-r];` (but of course you have to implement bound checks and wrap around). — Thomas Sablik, Feb 25 '21 at 08:43

score 1 · Accepted Answer · answered Feb 25 '21 at 08:50

There is one non standard usage in your code:

    int a[n];

Despite being accepted as extensions by gcc, VLA are not part of C++

Now for your question: instead of moving all the elements of the array, one step at a time, just note that you should move all only once by r%n steps. This would greatly reduce the time complexity, but you will have to allocate a second array:

...
int *a = new int[n];
int *result = new int[n];
...
r %= n;
for (int i=0; i<n; i++) {
    result[(i + r) % n] = a[i];
}
...

reduce the time complexity of below given code .The code working fine the problem is time complexity

1 Answers1