पायथन में सभी गेंदों को प्रत्येक बॉक्स में ले जाने के लिए न्यूनतम संचालन ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास boxes नामक एक बाइनरी स्ट्रिंग है, जहां boxes[i] '0' दर्शाता है कि i-वां बॉक्स खाली है, और '1' दर्शाता है कि इसमें एक गेंद है। अब, एक संचालन में, हम एक गेंद को एक बॉक्स से आसन्न बॉक्स में ले जा सकते हैं। ऐसा करने के बाद, कुछ बॉक्स में एक से अधिक गेंदें हो सकती हैं। हमें answer नामक आकार n की एक सरणी ढूंढनी है, जहां answer[i] i-वें बॉक्स में सभी गेंदों को ले जाने के लिए आवश्यक न्यूनतम संचालनों की संख्या है।

इसलिए, यदि इनपुट है boxes = "1101", तो आउटपुट [4, 3, 4, 5] होगा

• पहले बॉक्स पर सभी गेंदें डालने के लिए, हमें बॉक्स2 से एक संचालन में और अंतिम गेंद से तीन संचालन में लेना होगा, इसलिए कुल 4 संचालन।

• दूसरे बॉक्स पर सभी गेंदें डालने के लिए, हमें बॉक्स1 से एक संचालन में और अंतिम गेंद से दो संचालन में लेना होगा, इसलिए कुल 3 संचालन।

• तीसरे बॉक्स पर सभी गेंदें डालने के लिए, हमें बॉक्स2 और अंतिम से एक-एक संचालन में और बॉक्स1 से दो संचालन में लेना होगा, इसलिए कुल 4 संचालन।

• अंतिम बॉक्स पर सभी गेंदें डालने के लिए, हमें बॉक्स1 से तीन संचालन में और बॉक्स2 से दो संचालन में लेना होगा, इसलिए कुल 5 संचालन।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• left := 0, right := 0, dist := 0

• i को 0 से boxes के आकार - 1 तक के लिए, करें

  • यदि boxes[i], "1" के समान है, तो

    • dist := dist + i

    • यदि i, 0 के समान है, तो

      • left := left + 1

    • अन्यथा,

      • right := right + 1

• arr := एक सूची और प्रारंभ में इसमें dist डालें

• i को 1 से boxes के आकार - 1 तक के लिए, करें

  • arr[i-1] + left - right को arr के अंत में डालें

  • यदि boxes[i], "1" के समान है, तो

    • left := left + 1

    • right := right - 1

• arr वापस करें

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(boxes):
    left = 0
    right = 0
    dist = 0
    for i in range(len(boxes)):
        if boxes[i] == "1":
            dist += i
            if i == 0:
                left += 1
            else:
                right += 1
    arr = [dist]
    for i in range(1, len(boxes)):
        arr.append(arr[i-1] + left - right)
        if boxes[i] == "1":
            left += 1
            right -= 1
    return arr

boxes = "1101"
print(solve(boxes))

इनपुट

"1101"

आउटपुट

[4, 3, 4, 5]