Tìm số lớn nhất nhỏ hơn N có cùng bộ chữ số trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi N đại diện cho một số. Nhiệm vụ của chúng ta là tìm số lớn nhất nhỏ hơn N có cùng bộ chữ số.

Mô tả sự cố: chúng ta cần tìm một số có tất cả các chữ số của số đã cho, đó là số lớn nhất nhỏ hơn N.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: N =“54314”

Đầu ra: 54341

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tìm chữ số của số có thể di chuyển để tìm số lớn nhất nhỏ hơn. Bây giờ, con số phải lớn hơn thành công đúng của nó để giải quyết mục đích.

Đối với điều này, chúng tôi sẽ duyệt qua dạng số từ phải sang trái và tìm phần tử lớn hơn các phần tử cuối cùng.

Sau đó, tìm phần tử lớn nhất trong mảng con bên phải và thay thế nó bằng phần tử hiện tại. Sau khi sắp xếp, mảng con là một thứ tự giảm dần. Đây sẽ là yếu tố nhỏ hơn tuyệt vời nhất của bạn.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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<char>());

   cout<<"The Greatest smaller number with same set of digits is "<<N;

   return;
}

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

   return 0;
}

Đầu ra

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