Insert Five

Given a number, insert a 5 at any position of the number to make the number after insertion the largest

Question

Given a number, insert a 5 at any position of the number to make the number after insertion the largest

Example:

Input:  a = 234
Output: 5234

Analyzation

Divide the solution to whether the number is positive or negative. If the number is positive, then check from the left and compare the digit with 5. If the digit is smaller than 5, put the 5 before that digit. If the number is negative, then check from the left and compare the digit with 5. If the digit is greater than 5, put the 5 before that digit.

The Code

class Solution:
    """
    @param a: A number
    @return: Returns the maximum number after insertion
    """
    def InsertFive(self, a):
        # write your code here
        astr = str(a)
        
        if a >= 0:
            for i in range(len(astr)):
                if int(astr[i]) <= 5:
                    new_str = astr[:i] + "5" + astr[i:]
                    break
        else:
            for i in range(1, len(astr)):  # start from the character after the "-" sign
                if int(astr[i]) >= 5:
                    new_str = astr[:i] + "5" + astr[i:]
                    break
        
        return int(new_str)

Time & Space Complexity

• Time complexity: O(n). Remember that the best case of a Binary Tree is O(logn) since it is a balanced tree but the worst case is O(n) because it can skew to only one side.
• Space complexity: O(n). Remember that the space complexity is always about how many nodes there are in a Binary Tree. If the tree is well-balanced then it is O(logn) but the worst case will be O(n).