परम्यूटेशन ऐरे के अनुसार बिट्स सेट करते हुए, साइज़ M के 1s के कंटीज्युअस ग्रुप का लेटेस्ट स्टेप ढूंढें।
एल्गोरिदम
lऔरrऐरे: प्रत्येक पोजीशन के लिए बाएं/दाएं कंटीज्युअस 1s की लंबाई।- प्रत्येक स्टेप पर करंट बिट सेट करें, पड़ोसियों से लंबाई मर्ज करें।
num= साइज़ M के ग्रुप्स की संख्या ट्रैक करें।- अगर
num > 0तोans = max(ans, step)अपडेट करें। - बाउंडरी अपडेट:
l[left_boundary]औरr[right_boundary]।
उदाहरण कोड
def solve(arr, m):
n = len(arr)
num = 0
ans = -1
l = [0] * n
r = [0] * n
for i in range(n):
cur = 1
idx = arr[i] - 1
if r[idx] == m: num -= 1
if l[idx] == m: num -= 1
cur += l[idx] + r[idx]
num += cur == m
if num > 0:
ans = max(ans, i + 1)
if idx - l[idx] > 0:
r[idx - l[idx] - 1] = cur
if idx + r[idx] < n - 1:
l[idx + r[idx] + 1] = cur
return ans
# टेस्ट: arr=[3,5,1,2,4], m=3 -> आउटपुट: 4
इनपुट/आउटपुट
इनपुट: arr=[3,5,1,2,4], m=3
आउटपुट: 4 (स्टेप 4 पर "11101" में "111" ग्रुप है)
