Problems

Write a function that takes a positive integer and returns the next smaller positive integer containing the same digits.

For example:

next_smaller(21) == 12
next_smaller(531) == 513
next_smaller(2071) == 2017

Return -1 (for Haskell: return Nothing, for Rust: return None), when there is no smaller number that contains the same digits. Also return -1 when the next smaller number with the same digits would require the leading digit to be zero.

next_smaller(9) == -1
next_smaller(135) == -1
next_smaller(1027) == -1  # 0721 is out since we don't write numbers with leading zeros

• some tests will include very large numbers.
• test data only employs positive integers.

Source

Kata – 4 kyu

https://www.codewars.com/kata/5659c6d896bc135c4c00021e/train/python

Tags

STRINGS, MATHEMATICS, TWO POINTERS

Methodology

Analyze the problem and find out:

1. Which scenarios that it won’t be produce next smaller integers?
2. Procedures on Getting the Next Smaller Number

Scenarios that the integer does not have the next smaller integers

1. When the integers have strict increasing digits, e.g. 135. In such case, any swap digits will produce a integer number that is bigger than the original number. (This should be easy to figure out)
2. The swapped number causes the reduce number of digits. e.g. 100 should goes to 10, but 10 is double digits and hence not qualified.

Procedures on Getting the Next Smaller Number

1. First we can find out the index of digit that we should be swapped from. From example, 531 → 513, we can learn that the swap_from index should be the first index starting from the right that has the larger num than the next digit. From the example, we can find that 3 is greater than 1, so index of 3 should be the swap_from index.
2. Next we should locate the swap_to index, this index should be swapped from the swap_from index. And for example, 603 → (306) → 360, we learn that the swap_to index should be the first index starting from right that is smaller than the digit that needs to be swapped. In this example, 3 should be the value that get swapped from 6
3. From the above example, after swapping, we observe that 306 needs to be further changed to 360, the idea behind this is to make sure the number is largest after the swap_from index since we are getting the next smaller number, swapping index guarantees that the number is smaller than original one, and getting the largest substring after swap_from index make sure we are getting the right number

Other Caveats

1. Convert the integer to list of string (characters) for easy swapping digit
2. Check if we can find swap_from index, if no condition met, we can terminate early as it is not possible to get next smaller number, e.g. 135
3. Check if number of the digits reduced, if so, then return -1

Solutions

def next_smaller(n):
		# convert the integer into list of characters
    l = list(str(n))
    # initialize the swap_from to -1
    swap_from = -1
    # starting backwards, check if the first digit 
    # is larger than the second digit, if so, set 
    # the swap_from index
    for i in range(len(l)-1, 0, -1):
        if l[i-1] > l[i]:
            swap_from = i-1
            break
    
    # if swap_from is not found, return -1
    if swap_from == -1:
        return -1
    
    # starting backwards, check if the digit is smaller
    # than the swap_from value, if so, set
    # the swap_to index
    for i in range(len(l)-1, -1, -1):
        if l[swap_from] > l[i]:
            swap_to = i
            break
    
    # swap two index
    l[swap_from], l[swap_to] = l[swap_to], l[swap_from]
    
    # sort the digit after swap_from index to have
    # the decreasing order
    ll = l[:swap_from+1] + sorted(l[swap_from+1:], reverse=True)
    
    # convert the list of chars to string
    s = ''.join(ll)
    # return -1 if the number of digit is not reduced after
    # convert to string
    return int(s) if len(str(n)) == len(str(int(s))) else -1