Python में अधिकतम k आसन्न स्वैप के बाद न्यूनतम संभव पूर्णांक खोजने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग num है जो एक बहुत बड़ी पूर्णांक संख्या को दर्शाती है और एक मान k भी है। हम मान के किन्हीं दो आसन्न अंकों को अधिकतम k बार स्वैप कर सकते हैं। हमें वह न्यूनतम मान ढूंढना है जो हम प्राप्त कर सकते हैं।

उदाहरण के लिए, यदि इनपुट है num = "5432" और k = 4, तो आउटपुट 2453 होगा क्योंकि:

पहले संख्या है 5432
पहले चरण के बाद: 4532
दूसरे चरण के बाद: 4523
तीसरे चरण के बाद: 4253
अंतिम चरण के बाद: 2453

समाधान के चरण

min_num := num के अंकों को सॉर्ट करें
i := 0, to_find := 0
while num != min_num and k > 0 and i < len(num):
- indx := num में इंडेक्स i से to_find आइटम का इंडेक्स
- while indx != -1:
  - यदि indx - i <= k, तो:
    - num := num[:i] + num[indx] + num[i:indx] + num[indx+1:]
    - k := k - (indx - i)
    - i := i + 1
    - to_find := 0
    - indx := num.find(str(to_find), i)
  - अन्यथा, लूप से बाहर निकलें
- to_find := to_find + 1
num वापस करें

उदाहरण

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

def solve(num, k):
    min_num = sorted(list(num))
    min_num = ''.join(min_num)
    i = 0
    to_find = 0
    while num != min_num and k > 0 and i < len(num):
        indx = num.find(str(to_find), i)
        while indx != -1:
            if indx - i <= k:
                num = num[:i] + num[indx] + num[i:indx] + num[indx+1:]
                k -= (indx - i)
                i += 1
                to_find = 0
                indx = num.find(str(to_find), i)
            else:
                break
        to_find += 1
    return num

num = "5432"
k = 4
print(solve(num, k))

इनपुट

"5432", 4