Based on the priority of the numbers, the translation is as follows: Next larger number based on the priority of the numbers

In the normal number system, 0 is the smallest number and 9 is the largest number. In this problem we will get a list of length 10, from index 0 to index 9 represents a number which represents the priority of that number, the list will be in increasing order which means the number appearing at the last index has Highest priority. We will also be given a number and we need to find the next number that is slightly larger than the current number.

Input 1: 
Given number = “123”
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132

Explanation

From the given priority array, we can see that 1 has priority greater than 2 and 3. 3 has higher priority than 2. So if the next permutation of a given number will be achieved by swapping 2 and 3.

Input 2:
Given number = 132
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132

Explanation

From the given priority array, we can see that the priority of 1 is greater than both 2 and 3. Priority of 3 is greater as compared to of 2. So, there will be no next permutation available.

method

In this approach, we will use the concept of the standard template library (STL) provided by the C programming language to get the next permutation. Let us see the steps −

• First, we will get the number of the next number, and an array representing the priority of the numbers in ascending order.

• We will call the predefined function to find the next number that is greater than the current given number.

• We will define a function that take the parameter given number and array.

• We will define a global array and store the priority of each digit taken from the given array to use later.

• We will convert the given number into a string in order to apply the next permutation function on it.

• We will define a custom function that will used to compare the characters of the string in the next permutation function of the stl.

• After getting the next permutation, we will convert the string to an integer and return it.

The Chinese translation of

Example

is:

Example

#include <bits/stdc++.h>
using namespace std;
// priority array or array in which the priority of each digit will be stored 
int prio[10];
// defining the compare function 
bool compare(char& a, char& b){
   return prio[a-'0'] < prio[b-'0'];
}
// function to get the next permuatation 
int nextNum(int n, int arr[]){
   for(int i=0; i<10; i++){
      prio[arr[i]] = i;
   }
   // converting the given number into string 
   string str = to_string(n);
   // calling the next permuatation stl function for the given string we will compare by custom function 
   bool cur = next_permutation(str.begin(),str.end(),compare);
   if(cur == false){
      // indicating the next permutation does not exist 
      return n;
   }
   n = stoi(str); // converting string back to number 
   return n;
}
int main(){
   int n = 312; // the given number 
   int arr[] = {9, 2, 3, 6, 8, 1, 0, 5, 4, 7}; // given array
   cout<<"The next number or permutation for the given number is: "<<nextNum(n, arr);
   return 0;
}

Output

The next number or permutation for the given number is: 123

Time and Space Complexity

The time complexity of the above code is O(N), where N is the number of digits in the given number.

The space complexity of the above code is O(N) because we are creating a new string to use the next permutation function.

Note: If the current number is the greater number among all the permutations then the next permutation function will return false and we will return the same number as the next permutation does not exist.

in conclusion

In this tutorial we implemented a code to find the next number which is greater than the current number but the priority of the numbers is not in order from 0 to 9 but is given in a separate array. We used the STL function next_permutation and a custom function to get the next number based on the new priority. The time and space complexity of the above code is O(number of digits).

The above is the detailed content of Based on the priority of the numbers, the translation is as follows: Next larger number based on the priority of the numbers. For more information, please follow other related articles on the PHP Chinese website!