{"id":454,"date":"2020-06-10T10:43:45","date_gmt":"2020-06-10T10:43:45","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=454"},"modified":"2022-03-23T23:05:36","modified_gmt":"2022-03-23T23:05:36","slug":"greater-and-least","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/greater-and-least\/","title":{"rendered":"Greater And Least"},"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. \n
    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>.   <\/p>\n<\/li>\n
  2. \n
    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>.<\/p>\n<\/li>\n
  3. \n
    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.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. \n
      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<\/sup>index digit.  <\/p>\n<\/li>\n
    2. \n
      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<\/sup> 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>).<\/p>\n<\/li>\n
    3. \n
      Swap digits at ith<\/sup> and jth<\/sup> index. After swapping 125321<\/code> becomes 135221<\/code>.<\/p>\n<\/li>\n
    4. \n
      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.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      OPTIMIZATIONS:<\/h3>\n
      \n
        \n
      1. \n
        A few optimizations can be made in this approach and significantly improve the Time Complexity<\/code> of the approach.  <\/p>\n<\/li>\n
      2. \n
        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>.<\/p>\n<\/li>\n
      3. \n
        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.<\/p>\n<\/li>\n
      4. \n
        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>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
        SOLUTIONS:<\/h3>\n\t\t\t\t\t\t