C++ में वृत्ताकार सरणी लूप

मान लीजिए हमारे पास धनात्मक और ऋणात्मक पूर्णांकों की एक वृत्ताकार सरणी nums है। यदि इंडेक्स पर संख्या k धनात्मक है, तो k कदम आगे बढ़ें। यदि ऋणात्मक (-k) है, तो k कदम पीछे जाएँ। सरणी वृत्ताकार है। हमें जांचना है कि क्या nums में एक लूप (चक्र) मौजूद है। एक चक्र की लंबाई > 1 होनी चाहिए और उसी इंडेक्स पर शुरू और खत्म होना चाहिए।

उदाहरण: [2,-1,1,2,2] → true (चक्र: 0 → 2 → 3 → 0, लंबाई 3)।

फास्ट-स्लो पॉइंटर (फ्लॉयड का चक्र खोज)

1. n = nums.size()। यदि n < 2 तो false।
2. सभी तत्वों को nums[i] %= n करें (कदमों को सामान्य करें)।
3. प्रत्येक इंडेक्स i के लिए:
   • यदि nums[i] == 0, तो जारी रखें।
   • slow = i, fast = i।
   • while nums[slow]*nums[fast] > 0 && nums[next(fast)]*nums[slow] > 0 (समान दिशा):
     • slow = next(slow), fast = next(next(fast))।
     • यदि slow == fast:
       • यदि slow == next(slow) (लंबाई 1), तो ब्रेक।
       • true लौटाएँ।
   • दिशा बदलने वाले सभी नोड्स को 0 से मार्क करें (विज़िटेड)।
4. false लौटाएँ।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int next(vector<int>& nums, int i) {
        int n = nums.size();
        return (n + nums[i] + i) % n;
    }
    
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return false;
        for (int i = 0; i < n; i++) nums[i] %= n;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            while (nums[slow] * nums[fast] > 0 && nums[next(nums, fast)] * nums[slow] > 0) {
                slow = next(nums, slow);
                fast = next(nums, next(nums, fast));
                if (slow == fast) {
                    if (slow == next(nums, slow)) break;
                    return true;
                }
            }
            // मार्क विज़िटेड
            int x = nums[i];
            slow = i;
            while (nums[slow] * x > 0) {
                int temp = next(nums, slow);
                nums[slow] = 0;
                slow = temp;
            }
        }
        return false;
    }
};

int main() {
    vector<int> v = {2,-1,1,2,2};
    Solution ob;
    cout << ob.circularArrayLoop(v); // 1 (true)
    return 0;
}

इनपुट

[2,-1,1,2,2]

आउटपुट

1