Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 동일한 자릿수로 다음으로 큰 수 찾기

<시간/>

이 문제에서 요소 N이 주어집니다. 동일한 자릿수 집합을 가진 다음 큰 숫자를 찾아야 합니다. N보다 큰 같은 자릿수를 가진 가장 작은 수를 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

N = "92534"

출력

92543

솔루션 접근 방식

다음으로 더 큰 요소를 찾기 위한 문제에 대한 간단한 해결책은 다음과 같은 접근 방식을 사용하는 것입니다 -

  • 최하위 비트에서 최상위 비트로 숫자를 순회합니다. 그리고 현재 요소가 마지막 요소보다 작으면 중지합니다.

  • 이 검색 후에 나머지 배열에서 가장 작은 요소를 찾습니다. 그리고 가장 작은 숫자를 찾아 그 숫자로 바꿉니다.

  • 그런 다음 나머지 하위 배열을 정렬하고 출력을 반환합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#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;
}

출력

The next number with same set of digits is 92543