মান লাগিয়ে, আমাদের একটি অ্যারে arr আছে যা 1 থেকে n পর্যন্ত সংখ্যার পারমুটেশন ধারণ করে। যদি আমাদের একটি বাইনারি স্ট্রিং থাকে যার আকার n এবং শুরুতে এর সব বিট শূন্য। এখন প্রতিটি ধাপ i-তে (ইন্ডেক্সিং ১ থেকে শুরু হয় বাইনারি স্ট্রিং এবং arr উভয়ের জন্য) 1 থেকে n পর্যন্ত, arr[i] পজিশনের বিট ১ করা হয়। আমাদের আরেকটি মান m আছে, এবং আমাদের সেই সর্বশেষ ধাপটি বের করতে হবে যেখানে আকার m-এর একটি গ্রুপ অফ Ones থাকে। এখানে গ্রুপ অফ Ones মানে ১-র একটি কন্টিগুয়াস সাবস্ট্রিং যা যেকোনো দিকেই এক্সটেন্ড করা যাবে না। আমাদের সঠিক আকার m-এর একটি গ্রুপ অফ Ones থাকা সর্বশেষ ধাপটি বের করতে হবে। যদি ऐसा কোনো গ্রুপ না পাই, তবে -1 রিটার্ন করুন।
যেমন, ইনপুট arr = [3,5,1,2,4], m = 3 হলে, আউটপুট হবে 4 কারণ, প্রারম্ভিক বাইনারি স্ট্রিং "00000" তারপর ধাপগুলো:
- "00100", গ্রুপস: ["1"]
- "00101", গ্রুপস: ["1", "1"]
- "10101", গ্রুপস: ["1", "1", "1"]
- "11101", গ্রুপস: ["111", "1"]
- "11111", গ্রুপস: ["11111"]
এখানে আকার ৩-এর একটি গ্রুপ থাকা সর্বশেষ ধাপ হল ধাপ ৪।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- n := arr-এর আকার
- num := 0
- ans := -1
- l := আকার n-এর একটি অ্যারে, ০ দিয়ে ভরা
- r := আকার n-এর একটি অ্যারে, ০ দিয়ে ভরা
- i = 0 থেকে n - 1 পর্যন্ত লুপ:
- cur := 1
- idx := arr[i] - 1
- যদি r[idx] == m হয়, তবে num := num - 1
- যদি l[idx] == m হয়, তবে num := num - 1
- cur := cur + l[idx] + r[idx]
- num := num + (cur == m)
- যদি num > 0 হয়, তবে ans := max(ans, i + 1)
- যদি idx - l[idx] > 0 হয়, তবে r[idx - l[idx] - 1] := cur
- যদি idx + r[idx] < n - 1 হয়, তবে l[idx + r[idx] + 1] := cur
- ans রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
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
print(solve(arr, m))
ইনপুট
[3,5,1,2,4], 3
আউটপুট
4
