Trong bài toán này, chúng ta được cung cấp một phần tử N. Chúng ta cần tìm số lớn hơn tiếp theo có cùng bộ chữ số. Chúng ta cần tìm số nhỏ nhất có cùng chữ số lớn hơn N.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = "92534"
Đầu ra
92543
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề để tìm ra phần tử lớn hơn tiếp theo là bằng cách tiếp cận sau -
-
Di chuyển số từ bit quan trọng nhất đến bit quan trọng nhất. Và dừng khi phần tử hiện tại nhỏ hơn phần tử cuối cùng.
-
Sau khi tìm kiếm phần tử nhỏ nhất trong mảng còn lại. Và tìm số nhỏ nhất và đổi nó với số.
-
Sau đó, sắp xếp mảng con còn lại và trả về kết quả.
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 <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void findNextGreater(char number[], int n) {
int i, j;
for (i = n-1; i > 0; i--)
if (number[i] > number[i-1])
break;
if (i==0) {
cout<<"Next number is not possible";
return;
}
int x = number[i-1], smallest = i;
for (j = i+1; j < n; j++)
if (number[j] > x && number[j] < number[smallest])
smallest = j;
char temp = number[smallest];
number[smallest] = number[i-1];
number[i-1] = temp;
sort(number + i, number + n);
cout<<number;
return;
}
int main(){
char number[] = "92534";
int n = strlen(number);
cout<<"The next number with same set of digits is ";
findNextGreater(number, n);
return 0;
} Đầu ra
The next number with same set of digits is 92543