পাইথনে বাইনারি স্ট্রিংয়ে ১ গুলো গ্রুপ করতে ন্যূনতম স্ব্যাপ

একটি বাইনারি স্ট্রিংয়ে সব ১ গুলো একসাথে আনার জন্য ন্যূনতম এডজেসেন্ট স্ব্যাপের সংখ্যা বের করুন।

ইনপুট উদাহরণ

input_str = "10110101"

আউটপুট: 4

সোয়াপ সিকোয়েন্স

10110101 → 01110101 → 01111001 → 01111010 → 01111100

অ্যালগরিদম

1. সব ১-এর পজিশন সংগ্রহ করুন।
2. মিডিয়ান পজিশন বের করুন।
3. প্রতিটি ১-এর দূরত্ব মিডিয়ান থেকে বিয়োগ করুন তার ইনডেক্স দূরত্ব।
4. সামান্য ফলাফল হলো ন্যূনতম স্ব্যাপ।

পাইথন কোড

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'))  # 4

ব্যাখ্যা

মিডিয়ান পজিশনে ১ গুলো কেন্দ্রীভূত করলে মোট দূরত্ব ন্যূনতম হয়। এটি Minimum Moves to Group All 1's সমস্যার সমাধান।