[AlgoExpert] Single Cycle Search

Single Cycle Search

  • Time : O(n)
  • Space : O(1)
1
2
3
4
5
6
7
8
9
10
11
bool hasSingleCycle(vector<int> array) {
int n = array.size();
int vis = 0, idx = 0;
while(vis < n) {
if(vis > 0 and idx == 0) return false;
vis++;
idx = ((array[idx] % n) + n + idx) % n;
}
return idx == 0;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/16/PS/AlgoExpert/single-cycle-check/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.