मान लीजिए हमें एक बाइनरी स्ट्रिंग input_str दी गई है जिसमें 0 और 1 हैं। हमारा कार्य दिए गए स्ट्रिंग में 1 को स्वैप करके 0 और 1 को समूहित करना है। हमें न्यूनतम संख्या में स्वैप ऑपरेशन करने हैं, और हमें वह मान लौटाना है। एक बात ध्यान रखें, हम केवल आसन्न मानों को स्वैप कर सकते हैं।
इसलिए, यदि इनपुट है input_str = "10110101", तो आउटपुट होगा 4।
स्वैप निम्नलिखित जैसा होगा:
10110101 -> 01110101 -> 01111001 -> 01111010 -> 01111100
कुल स्वैप की संख्या: 4।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
one :=एक नई सूची जिसमेंinput_strमें उन स्थितियाँ हों जहां 1 स्थित हैंmid := floor(one का आकार / 2)res := 0iके लिए 0 सेoneके आकार तक की रेंज में, करें:res := res + |one[mid] - one[i]| - |mid - i|
- यदि
res < 0, तो:0लौटाएं
- अन्यथा:
resलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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