{"id":1596,"date":"2020-07-01T09:31:13","date_gmt":"2020-07-01T09:31:13","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1596"},"modified":"2022-03-25T10:38:20","modified_gmt":"2022-03-25T10:38:20","slug":"next-greater-same-digit","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/next-greater-same-digit\/","title":{"rendered":"Next Greater Same Digit"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Searching<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a number N<\/code>, find the smallest number that has same set-of-digits as N<\/code> and is greater than N<\/code>. If N<\/code> is the greatest possible number with its set-of-digits, then print the same number N<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input  : "12345"\n\nOutput : "12354"<\/code><\/pre>\n
Input  : "54321"\n\nOutput : "54321"\n\nExplanation : No number is greater than 54321 with same set of digits, thats why print same number.<\/code><\/pre>\n
Input  : "12321"\n\nOutput : "13122"<\/code><\/pre>\n
OBSERVATIONS<\/strong>:<\/p>\n
\n
    \n
  1. If the digits are all sorted in strictly descending order, then the number itself would be our answer as there is no bigger number than that.
    \nFor example, 54321<\/code>.   <\/li>\n
  2. If the digits are all sorted in strictly increasing order, then just swap the last two digits. For example, 12345<\/code> will change to 12354<\/code>.<\/li>\n
  3. For all other cases, we need to process all the digits in the number from right to left as we need to find the smallest of the greater numbers.<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. Start traversing the given number from rightmost digit till you reach a digit that is just smaller than its right digit, say index of this digit be i<\/code>.
      \nFor example<\/em><\/strong>:
      \nN<\/code> =<\/code> 125321<\/code>, here if we scan from right to left, 2<\/code> is the first digit that is less than 5<\/code> so 2<\/code> is our ith<\/code> index digit.  <\/li>\n
    2. Now again traverse to the right of this index i<\/code> and find the smallest digit that is just greater than the digit at ith<\/code> index. Let’s say the found index is j<\/code> at the right of i<\/code>. Now if we traverse right of 2<\/code>, the smallest digit that is greater than 2<\/code> is 3<\/code> (not 5<\/code>).<\/li>\n
    3. Swap digits at ith<\/code> and jth<\/code> index. After swapping 125321<\/code> becomes 135221<\/code>.<\/li>\n
    4. Sort digits from (i+1)<\/code> to the rightmost index in increasing order. After sorting, 135221<\/code> becomes 131225<\/code>, which is our required solution.<\/li>\n<\/ol>\n<\/blockquote>\n
      OPTIMIZATIONS:<\/h3>\n
      \n
        \n
      1. A few optimizations can be made in this approach and significantly improve the Time Complexity<\/code> of the approach.  <\/li>\n
      2. The Linear Search<\/code> used in Step-2<\/code> can be replaced with Binary Search<\/code> as the right digits are already sorted. This reduces Time Complexity<\/code> from O(n)<\/code> to O(logn)<\/code>.<\/li>\n
      3. The Sorting<\/code> used in Step-4<\/code> can be done in O(n)<\/code> instead of O(nlogn)<\/code> as only one digit needs to be repositioned else all are already sorted.<\/li>\n
      4. This Optimization<\/code> would improve our solution from O(n+n+nlogn)<\/code> to O(n+logn+n)<\/code> giving overall time complexity of O(n)<\/code>, where
        \nn = number-of-digits-of-a-given-number<\/code>.<\/li>\n<\/ol>\n<\/blockquote>\n
        SOLUTIONS:<\/h3>\n
        \t\t\t\t\t\t