मान लीजिए हमारे पास nums नामक एक सर्कुलर सूची है। इसलिए पहला और अंतिम तत्व पड़ोसी हैं। इसलिए किसी भी इंडेक्स i से शुरू करके, हम nums[i] संख्या में कदम आगे बढ़ सकते हैं यदि nums[i] एक धनात्मक मान है, अन्यथा पीछे यदि यह ऋणात्मक मान है। हमें जांचना है कि क्या एक चक्र है जिसकी लंबाई एक से अधिक है जैसे कि पथ केवल आगे जाता है या केवल पीछे जाता है।
इसलिए, यदि इनपुट है nums = [-1, 2, -1, 1, 2], तो आउटपुट होगा True, क्योंकि एक फॉरवर्ड पथ [1 -> 3 -> 4 -> 1] है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
n := numsका आकार- यदि
n0 के समान है, तो:Falseलौटाएं
seen :=आकारnकी एक सरणी और 0 से भरेंnumsको प्रत्येक तत्वxके लिएx mod nप्राप्त करके अपडेट करेंiter := 0iके लिए 0 सेn - 1तक की रेंज में, करें:- यदि
nums[i]0 के समान है, तो:- अगले पुनरावृत्ति के लिए जाएं
iter := iter + 1pos := Trueneg := Truecurr := i- निम्नलिखित को बार-बार करें:
- यदि
nums[curr]औरseen[curr]iterके समान है, तो:Trueलौटाएं
- यदि
seen[curr]शून्येतर है, तो:- लूप से बाहर निकलें
- यदि
nums[curr] > 0, तो:neg := False
- अन्यथा:
pos := False
- यदि
negऔरposदोनों गलत हैं, तो:- लूप से बाहर निकलें
seen[curr] := itercurr := (curr + nums[curr] + n) mod n- यदि
nums[curr]0 के समान है, तो:- लूप से बाहर निकलें
- यदि
- यदि
Falseलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def solve(nums):
n = len(nums)
if n == 0:
return False
seen = [0]*n
nums = [x % n for x in nums]
iter = 0
for i in range(n):
if nums[i] == 0:
continue
iter += 1
pos = True
neg = True
curr = i
while True:
if nums[curr] and seen[curr] == iter:
return True
if seen[curr]:
break
if nums[curr] > 0:
neg = False
else:
pos = False
if not neg and not pos:
break
seen[curr] = iter
curr = (curr + nums[curr] + n) % n
if nums[curr] == 0:
break
return False
nums = [-1, 2, -1, 1, 2]
print(solve(nums))
इनपुट
[-1, 2, -1, 1, 2]
आउटपुट
True