为什么我的算法将数组右转 k 次而无需 O(n) 中的额外数组 运行 仅适用于小数组而不适用于大数组？

Question

我正在尝试解决 HackerEarth (here) 上给出的 Monk and Rotation 问题，我知道其他算法在市场上可以为我完成这项工作，但我尝试制作一种新的有效算法，用于将数组元素向右旋转 k 次 而不使用另一个数组并且没有使用任何自定义库函数 并尝试在 O(n) 中 运行 它。所以，我想出了我的解决方案，我从数组的第一个元素开始，并使用 temp 变量来存储第一个元素，然后交换 temp 与旋转后将出现在数组索引处的元素，然后在旋转后再次与该特定元素的下一个位置交换，依此类推...我在 temp 时停止变量等于给定数组的起始元素。

注意：我假设所有元素都是不同的

但问题是它在我的本地系统中对我有效，并且还通过了 HackerEarth 网站上提到的测试用例，但我无法通过那里的其余私有测试用例。

---

下面是我的代码供大家参考：

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

测试用例示例：

1 
5 2
1 2 3 4 5

我的输出：

4 5 1 2 3 

Answer 1

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

因为不能保证通过重复 i = (i+k)%n 增量您将访问所有元素。

更具体地说，这仅在 n 和 k 没有公约数（1 除外）时有效。

例如，如果 n = 4 且 k = 2，则永远不会访问数组的奇数索引。