SHOW:
|
|
- or go back to the newest paste.
| 1 | /* | |
| 2 | Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1. | |
| 3 | ||
| 4 | Input format | |
| 5 | A 32 bit integer N | |
| 6 | ||
| 7 | Output format | |
| 8 | A single integer | |
| 9 | ||
| 10 | Sample Input 1 | |
| 11 | 12 | |
| 12 | ||
| 13 | Sample Output 1 | |
| 14 | 21 | |
| 15 | ||
| 16 | Explanation | |
| 17 | There is only one number greater than 12 which is composed of 2 and 1 and it is 21. | |
| 18 | ||
| 19 | Constraints | |
| 20 | 0<= N <= 10^9 | |
| 21 | */ | |
| 22 | ||
| 23 | vector<int> getDigits(int n) {
| |
| 24 | vector<int> digits; | |
| 25 | while (n > 0) {
| |
| 26 | digits.push_back(n % 10); | |
| 27 | n /= 10; | |
| 28 | } | |
| 29 | reverse(digits.begin(), digits.end()); | |
| 30 | return digits; | |
| 31 | } | |
| 32 | ||
| 33 | /** | |
| 34 | * @param {number} n
| |
| 35 | * @return {number}
| |
| 36 | */ | |
| 37 | // https://www.youtube.com/watch?v=LuLCLgMElus ; TUF | |
| 38 | function nextGreaterElementWithSameSetOfDigits(n) {
| |
| 39 | let arr=getDigits(n); | |
| 40 | let length=arr.length; | |
| 41 | if(length<=1) | |
| 42 | return -1; | |
| 43 | let index1,index2; | |
| 44 | let i=length-2,j; | |
| 45 | while(i>=0&&arr[i]>=arr[i+1]){
| |
| 46 | i--; | |
| 47 | } | |
| 48 | index1=i; | |
| 49 | if(index1>=0){
| |
| 50 | i=length-1; | |
| 51 | while(i>=0&&arr[i]<=arr[index1]){
| |
| 52 | i--; | |
| 53 | } | |
| 54 | index2=i; | |
| 55 | [arr[index1],arr[index2]]=[arr[index2],arr[index1]]; | |
| 56 | } | |
| 57 | else | |
| 58 | return -1; | |
| 59 | ||
| 60 | // reverse after index1+1; | |
| 61 | i=index1+1; | |
| 62 | j=length-1; | |
| 63 | while(i<j){
| |
| 64 | [arr[i],arr[j]]=[arr[j],arr[i]]; | |
| 65 | i++; | |
| 66 | j--; | |
| 67 | } | |
| 68 | return parseInt(arr.join(''));
| |
| 69 | ||
| 70 | ||
| 71 | } | |
| 72 | /* | |
| 73 | function nextGreaterElementWithSameSetOfDigits(n) {
| |
| 74 | let arr=getDigits(n); | |
| 75 | // console.log(arr);// order of digit should be inPlace | |
| 76 | let i,j; | |
| 77 | let length=arr.length; | |
| 78 | let hasFound=false; | |
| 79 | if(n<10) | |
| 80 | return -1; | |
| 81 | for(let i=length-1;i>=0;i--){
| |
| 82 | for(let j=i-1;j>=0;j--){
| |
| 83 | if(arr[i]>arr[j]){
| |
| 84 | [arr[i],arr[j]]=[arr[j],arr[i]]; | |
| 85 | hasFound=true; | |
| 86 | break; | |
| 87 | } | |
| 88 | } | |
| 89 | if(hasFound) | |
| 90 | break; | |
| 91 | } | |
| 92 | if(!hasFound) | |
| 93 | return -1; | |
| 94 | return parseInt(arr.join(''));
| |
| 95 | } | |
| 96 | */ | |
| 97 | ||
| 98 | function main() {
| |
| 99 | const n = parseInt(readLine(), 10); | |
| 100 | console.log(nextGreaterElementWithSameSetOfDigits(n)); | |
| 101 | } | |
| 102 |