ধরা যাক একটি সার্কুলার অ্যারে nums আছে যা পজিটিভ এবং নেগেটিভ ইন্টিজার মান ধারণ করে। যদি কোনো ইনডেক্সে k একটি পজিটিভ সংখ্যা হয়, তবে k স্টেপ সামনে যাব। অন্যথায়, যদি এটি নেগেটিভ (-k) হয়, তবে k স্টেপ পেছনে যাব। যেহেতু অ্যারেটি সার্কুলার, আমরা ধরে নিতে পারি যে লাস্ট এলিমেন্টের পরবর্তী এলিমেন্ট হলো প্রথম এলিমেন্ট, এবং প্রথম এলিমেন্টের পূর্বের এলিমেন্ট হলো লাস্ট এলিমেন্ট। আমরা যাচাই করব যে nums-এ কোনো লুপ (সাইকেল) আছে কিনা। একটি সাইকেল অবশ্যই একই ইনডেক্সে শুরু ও শেষ হবে এবং সাইকেলের দৈর্ঘ্য > 1 হতে হবে। যদি ইনপুট হয় [2,-1,1,2,2], তবে আউটপুট হবে true, কারণ 0 -> 2 -> 3 -> 0 এর মতো দৈর্ঘ্য ৩ এর একটি সাইকেল আছে।
সমাধানের ধাপগুলো −
n := nums-এর আকার
যদি n < 2 হয়, তবে false রিটার্ন করব
i = 0 থেকে n-1 পর্যন্ত, nums[i] := nums[i] mod n
i = 0 থেকে n-1 পর্যন্ত
যদি nums[i] = 0 হয়, তবে পরবর্তী ইটারেশনে যাব continue;
slow = i, fast = i;
যখন nums[slow] * nums[fast] > 0 এবং nums[fast-এর next] * nums[slow] > 0
slow = slow-এর next
fast := fast-এর next-এর next
যদি slow = fast হয়, তবে
যদি slow = slow-এর next হয়, তবে লুপ থেকে বের হব
true রিটার্ন করব
x := nums[i]
slow := i
যখন nums[slow] * x > 0
temp := slow-এর next
slow-এর next := 0
slow := temp
false রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#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; int 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; } }; main(){ vector<int> v = {2,-1,1,2,2}; Solution ob; cout << (ob.circularArrayLoop(v)); }
ইনপুট
[2,-1,1,2,2]
আউটপুট
1
