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 |