时间戳

首页 > 解决方案 > 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?

c++ - 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?

问题描述

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

标签： c++arraysalgorithmtime-complexity

解决方案

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.

推荐阅读