ধরুন আমাদের একটি বাইনারি স্ট্রিং input_str দেওয়া হয়েছে যাতে 0s এবং 1s রয়েছে। আমাদের কাজ হল প্রদত্ত স্ট্রিং-এ 1s অদলবদল করে 0 এবং 1 গ্রুপ করা। আমাদের ন্যূনতম সংখ্যক সোয়াপ অপারেশন করতে হবে, এবং আমাদের সেই মানটি ফেরত দিতে হবে। একটি জিনিস মনে রাখতে হবে, আমরা শুধুমাত্র সন্নিহিত মানগুলিকে অদলবদল করতে পারি।
সুতরাং, যদি ইনপুটটি হয় input_str =10110101, তাহলে আউটপুট হবে 4
অদলবদল হবে নিম্নলিখিত −
এর মত10110101->01110101->01111001->01111010->01111100
অদলবদলের মোট সংখ্যা:4.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- এক :=একটি নতুন তালিকা যেখানে ইনপুট_স্ট্রের অবস্থান রয়েছে যেখানে 1s অবস্থিত রয়েছে
- মধ্য :=ফ্লোর মান (এক/২ এর আকার)
- res :=0
- আমি 0 থেকে এক আকারের রেঞ্জের জন্য,
- করুন
- res :=res + |one[mid] - one[i]| - |মধ্য - i|
- যদি res <0 হয়, তাহলে
- রিটার্ন 0
- অন্যথায়,
- রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(input_string):
one = [i for i in range(len(input_string)) if input_string[i] == "1"]
mid = len(one) // 2
res = 0
for i in range(len(one)):
res += abs(one[mid] - one[i]) - abs(mid - i)
return 0 if res < 0 else res
print(solve('10110101')) ইনপুট
'10110101'
আউটপুট
4
