পাইথন ব্যবহার করে M আকারের সর্বশেষ গ্রুপ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে অ্যারে আছে এটি 1 থেকে n পর্যন্ত সংখ্যার একটি স্থানান্তর ধারণ করছে। যদি আমাদের n আকারের একটি বাইনারি স্ট্রিং থাকে এবং প্রাথমিকভাবে এর সমস্ত বিট শূন্যতে সেট করা হয়। এখন প্রতিটি ধাপে i (ইনডেক্সিং শুরু হয় 1 থেকে বাইনারি স্ট্রিং এবং arr উভয়ের জন্য) 1 থেকে n পর্যন্ত, বিট অ্যাট পজিশন arr[i] 1 এ সেট করা হয়েছে। আমাদের আরও একটি মান m আছে, এবং আমাদের সর্বশেষটি খুঁজে বের করতে হবে। যে ধাপে m আকারের একদল রয়েছে। এখানে একদলের অর্থ হল 1s এর একটি সংলগ্ন সাবস্ট্রিং যাতে এটি উভয় দিকে বাড়ানো যায় না। আমাদের সর্বশেষ ধাপটি খুঁজে বের করতে হবে যেখানে ঠিক m দৈর্ঘ্যের একটি গ্রুপ রয়েছে। যদি আমরা এই ধরনের কোনো গ্রুপ খুঁজে না পাই, তাহলে -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"]

এখানে সর্বশেষ ধাপে যেখানে 3 আকারের একটি গ্রুপ বিদ্যমান তা হল ধাপ 4।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=arr এর আকার
সংখ্যা :=0
উত্তর :=-1
l :=n আকারের একটি অ্যারে, এবং 0 দিয়ে পূরণ করুন
r :=n আকারের একটি অ্যারে, এবং 0 দিয়ে পূরণ করুন
আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
- cur :=1
- idx :=arr[i] - 1
- যদি r[idx] m এর মত হয়, তাহলে
  - সংখ্যা :=সংখ্যা - 1
- যদি l[idx] m এর মত হয়, তাহলে
  - সংখ্যা :=সংখ্যা - 1
- cur :=cur + l[idx] + r[idx]
- num :=num + cur একই m
- যদি num> 0 হয়, তাহলে
  - ans :=সর্বাধিক উত্তর, i + 1
- যদি idx - l[idx]> 0, তারপর
  - r[idx - l[idx] - 1] :=cur
- যদি idx + r[idx]
  - l[idx + r[idx] + 1] :=cur
উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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