-1

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
Improve this question
8
  • Your algorithm doesn't work if (n % k) == 0 Commented Aug 1, 2021 at 8:22
  • Doesn't work when gcd(n, k) > 1. You need a completely different algorithm. Commented Aug 1, 2021 at 8:24
  • 2
    Who teaches #include <bits/stdc++.h> and typedef long long ll;? That's an awful way of writing C++ code. Why should I not #include <bits/stdc++.h>? See also this answer. Commented Aug 1, 2021 at 9:09
  • 2
    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. Commented Aug 1, 2021 at 9:14
  • 2
    @RadientBrain Because such typedefs make your code much harder to read. Compilers don't care, but people do. Commented Aug 1, 2021 at 13:36

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.