5 Best Ways to Find Maximum Number by Adding 5 at Any Place in Python

by

💡 Problem Formulation: How do we formulate a program to insert the digit ‘5’ into any position of a non-negative integer, such that the resulting integer is as large as possible? For example, given the input ‘268’, the output should be ‘5268’, and for ‘670’, the output should be ‘6750’.

Method 1: String Manipulation and Comparison

This method involves converting the integer into a string, and then iteratively checking the best spot to insert ‘5’ by comparing it against each character. The function definition findMaximumByAddingFive(number) demonstrates this approach.

Here’s an example:

def findMaximumByAddingFive(number):
    num_str = str(number)
    for i in range(len(num_str)):
        if '5' > num_str[i]:
            return int(num_str[:i] + '5' + num_str[i:])
    return int(num_str + '5')
  
print(findMaximumByAddingFive(268))

The output is:

5268

We convert the given integer to a string and iterate over its characters. Whenever we find a character (digit) smaller than ‘5’, we insert ‘5’ at that position and return the new integer. If ‘5’ is greater than all digits, we append it at the end.

Method 2: Using List Conversion

This technique involves converting the integer to a list of digits, finding the correct insertion point for ‘5’, and then constructing a new integer from the modified list. The function maxWithFiveInserted(number) utilises list conversion for this operation.

Here’s an example:

def maxWithFiveInserted(number):
    digits = list(str(number))
    for i, digit in enumerate(digits):
        if digit < '5':
            digits.insert(i, '5')
            break
    else:
        digits.append('5')
    return int(''.join(digits))

print(maxWithFiveInserted(670))

The output is:

6750

By treating the number as a list of its digits, we can easily insert ‘5’ at the correct position without having to deal with string slicing. We loop through the digits and when a digit less than ‘5’ is encountered, ‘5’ is inserted before it, otherwise at the end.

Method 3: Recursive Approach

The recursive method breaks down the problem into smaller sub-problems by stripping the last digit of the number until the base condition is met. The function insertFiveRecursively(number) illustrates recursion for inserting ‘5’.

Here’s an example:

def insertFiveRecursively(number):
    if number == 0 or number % 10 < 5:
        return number * 10 + 5
    return insertFiveRecursively(number // 10) * 10 + number % 10

print(insertFiveRecursively(764))

The output is:

7654

This method recursively divides the number by 10 until a digit less than ‘5’ is encountered, then it adds ‘5’ to this intermediate result. It’s a more mathematical approach, requiring a good understanding of recursion and number theory.

Method 4: Greedy Approach

In the greedy approach, we assume that the best local decision will lead to a globally optimal solution. The function insertFiveGreedy(number) uses a while loop to find the optimal spot for insertion.

Here’s an example:

def insertFiveGreedy(number):
    digits = []
    while number > 0:
        digits.append(number % 10)
        number //= 10
    for i in range(len(digits)):
        if digits[-i-1] < 5:
            digits.insert(len(digits)-i, 5)
            return int(''.join(map(str, reversed(digits))))
    digits.insert(0, 5)
    return int(''.join(map(str, digits)))

print(insertFiveGreedy(436))

The output is:

5436

We iteratively divide the number by 10 to get each digit, storing them in reversed order. Then, we traverse this list in reverse, inserting ‘5’ once we find the right spot. This greedy method ensures we find the first place where ‘5’ increases the number’s value.

Bonus One-Liner Method 5: Pythonic Way

Python’s expressive syntax allows us to perform the task in a single line using list comprehension and the max() function. This approach condenses Method 2 into a one-liner.

Here’s an example:

print(max(int(str(number)[:i] + '5' + str(number)[i:]) for i in range(len(str(number)) + 1)))

This one-liner checks all possible new numbers created by adding ‘5’ at every possible position and returns the maximum.

Summary/Discussion

  • Method 1: String Manipulation and Comparison. Simple and straightforward with immediate comparisons. Limited by string operations and not as efficient for very large numbers.
  • Method 2: Using List Conversion. Breaks the number down into a list of digits, making insertion operations more natural. It can be slower due to list manipulation and multiple conversions from and to strings.
  • Method 3: Recursive Approach. Elegant and mathematical, ideal for those familiar with recursive thinking. Not as intuitive for some, and can have a larger stack footprint for deep recursion.
  • Method 4: Greedy Approach. Intelligently finds the optimal insertion point without inspecting every character. However, reversing the list can add overhead for larger numbers.
  • Method 5: Pythonic One-Liner. Concise and showcases Python’s ability to condense logic into a single line. Readability may be an issue, and it’s not the most performance-efficient.