Why does my algorithm to rotate array right by k times without extra array running in O(n) work only for small arrays and not for big ones?

Question

I am trying to solve the Monk and Rotation problem given on HackerEarth (here) and I know other algorithms in the market that can do the work for me but I tried to make a new efficient algorithm for rotating array elements to the right by k times without using another array and without using any custom library functions and trying to run it in O(n). So, I came up with my solution where I started with the first element of the array and used a temp variable to store the first element and then swap temp with the element that will come at the array index after the rotation and then again swapping with the next position after rotation for that particular element and so on... I stop when the temp variable equals the starting element of the given array.

Note: I assume that all the elements are distinct

But the problem is that it works for me in my local system and also passes the test cases mentioned on the HackerEarth Website but I am not able to pass the rest of the private test cases there.

Below is my code for your reference:

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

int main() {
    ll t, temp;
    cin >> t;    //inputing test cases
    while(t--){
        vl arr;
        ll i,n,k;
        cin>>n>>k;
        for(i=0;i<n;i++){    //inputing array
            cin>>temp;
            arr.push_back(temp);
        }
        
        /*Main Algo*/
        ll temp1 = arr[0];
        temp = arr[0];
        while(1){
            i = (i+k)%(n);
            swap(arr[i], temp);
            //cout<<"temp: "<<temp<< endl;
            if(temp == temp1)break;
        }

        //Printing Rotated Array
        for(i=0;i<n;i++){
            cout<<arr[i]<<" ";
        }
    }
    return 0;
}

An example of the test case:

1 
5 2
1 2 3 4 5

My Output:

4 5 1 2 3

Doesn't work when gcd(n, k) > 1. You need a completely different algorithm. — trincot, Aug 01 '21 at 08:24
Actually I don't think, this is possible in O(n) without additional storage of at least O(k). Or you can do it in O(n*k) without any additional storage. — derpirscher, Aug 01 '21 at 08:39
Who teaches `#include ` and `typedef long long ll;`? That's an awful way of writing C++ code. [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) See also [this answer](https://stackoverflow.com/a/68159325/1625187). — Evg, Aug 01 '21 at 09:09
If you ever plan to write code for more than a hobby on competitive sites you'd do well to forget that `bits/stdc++.h` exists, delete all of those typedefs, and seriously consider if `using namespace std;` is worth the unexpected sadness it can cause. — Retired Ninja, Aug 01 '21 at 09:14
@Evg and @RetiredNinja I get the point of not using that `bits/stdc++.h` header but can you please point out why shouldn't I use the `typedef's`? I have seen [this](https://stackoverflow.com/q/516237/16570636) but couldn't get a reason to not use it here. I used it here to just avoid repetitive long initializations. — , Aug 01 '21 at 13:18
@RadientBrain Because such `typedef`s make your code much harder to read. Compilers don't care, but people do. — Evg, Aug 01 '21 at 13:36
@derpirscher: there are various O(n) algorithms which use O(1) storage. A few years back, I did a brief survey of rotation algos: https://stackoverflow.com/a/51660916/1566221 — rici, Aug 02 '21 at 00:14

score 2 · Accepted Answer · answered Aug 01 '21 at 08:28

Why my custom made algorithm [...] works only for small arrays and not for big arrays?

Because it is not guaranteed that with repeated i = (i+k)%n increments you will visit all elements.

More specifically, this will only work when n and k have no common divisor (other than 1).

For instance, if n = 4 and k = 2, then the odd indices of your array will never be visited.

Why does my algorithm to rotate array right by k times without extra array running in O(n) work only for small arrays and not for big ones?

1 Answers1