পাইথনে কাঙ্ক্ষিত সبدল বিনিময়ের মাধ্যমে ন্যূনতম পূর্ণসংখ্যা খুঁজে বের করার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি স্ট্রিং আছে num যা একটি খুব বড় পূর্ণসংখ্যা রিপ্রেজেন্ট করে এবং আরেকটি মান k। আমরা কোনো দুটি সন্নিহিত অঙ্ককে সর্বোচ্চ k বার বিনিময় করতে পারি। আমাদের যে ন্যূনতম মান পাওয়া সম্ভব সেটি বের করতে হবে।

যেমন, ইনপুট হলে num = "5432" এবং k = 4, তবে আউটপুট হবে 2453 কারণ প্রথমে সংখ্যাটি ছিল 5432। প্রথম ধাপে হবে 4532, তারপর 4523, আবার 4253 এবং শেষে 2453।

সমাধানের ধাপসমূহ

min_num := num-এর অঙ্কগুলো সর্ট করুন
i := 0, to_find := 0
num min_num-এর সমান না হওয়া পর্যন্ত, k > 0 এবং i < len(num) रहने পর্যন্ত লুপ চালান:
- indx := num-এ i ইন্ডেক্স থেকে to_find আইটেমটির ইন্ডেক্স
- 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-এ i থেকে to_find এর ইন্ডেক্স
  - অন্যথায়,
    - লুপ থেকে বের হয়ে যান
- 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