C++-এ একই ডিজিট দিয়ে N-র চেয়ে ছোট সর্বোচ্চ সংখ্যা বের করুন

অ্যালগরিদম: নেক্সট পারমিউটেশন (রিভার্স)

1. ডান থেকে বাম স্ক্যান করুন: প্রথমে এমন i খুঁজুন যাতে str[i] < str[i-1] (ডিক্রিজিং সিকোয়েন্স ভাঙল)।
2. যদি না পাওয়া যায় → সবচেয়ে ছোট পারমিউটেশনই, সমাধান নেই।
3. i-1-এ থাকা ডিজিটের ডানে যে সব ডিজিট str[i-1]-এর চেয়ে ছোট, তার মধ্যে সর্বোচ্চ খুঁজুন (জাস্ট ছোটটি)।
4. সেই ডিজিট দিয়ে str[i-1] 스ওয়াপ করুন।
5. i থেকে শেষ পর্যন্ত সাবঅ্যারে ডিক্রিজিং অর্ডারে সোর্ট করুন (রিভার্স করলে হয়ে যায় কারণ সেটা ইতিমধ্যে ইনক্রিজিং ছিল)।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

void calcGreatestSmallerElement(string N, int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        if (N[i] < N[i - 1]) break;
    if (i == 0) {
        cout << "Previous number is not possible";
        return;
    }
    int x = N[i - 1], greatest = i;
    for (j = i; j < size; j++)
        if (N[j] < x && N[j] > N[greatest])
            greatest = j;
    swap(N[greatest], N[i - 1]);
    sort(N.begin() + i, N.begin() + size, greater());
    cout << "The Greatest smaller number with same set of digits is " << N;
}

int main() {
    string N = "654232";
    int size = N.length();
    cout << "The number is " << N << endl;
    calcGreatestSmallerElement(N, size);
    return 0;
}

আউটপুট

The number is 654232
The Greatest smaller number with same set of digits is 654223

ব্যাখ্যা

• স্টেপ ১: ডান থেকে বামে প্রথম ডিক্রিজিং পেয়ার (২ < ৩) → i=5 (০-বেসড)।
• স্টেপ ২: N[4]=3-এর চেয়ে ছোট সবচেয়ে বড় ডিজিট ডানে খুঁজুন → 2 (ইনডেক্স ৫)।
• স্টেপ ৩: সওয়াপ → 654223।
• স্টেপ ৪: সাফিক্স সোর্ট (ডিক্রিজিং) → ইতিমধ্যে সোর্টেড।
• টাইম: O(n log n) (সোর্টের কারণে), O(n) করা যায় রিভার্স দিয়ে।

নোট

• লিডিং জিরো না হয় তা নিশ্চিত করুন (যদি ইনপুট নম্বর gültig হয়)।
• C++-এ prev_permutation STL ফাংশনও আছে।