CODEWITHSUNDEEP
python
J2015
J2015

Reputation: 330

How to concatenate a digit in the different indexes of a number?

I want to a add a digit to a number and return the maximum possible number after adding the new digit to this number. As an example by adding 3 to the following numbers get the max as follow:

Num = 26 should return 326

Num = 821 should return 8321

Num = 555 should return 5553

Num = -555 should return -3555

This is my solution:

def insertion(N, digit='3'):
    lst = []
    for i, x in enumerate(str(N)):
        if not N < 0:
            num_digit = str(N)
            num_digit = num_digit[:i] + digit + num_digit[i:]
        else:
            num_digit = str(abs(N))
            num_digit = '-' + (num_digit[:i] + digit + num_digit[i:])
        lst.append(int(num_digit))
    if not N < 0:
        lst.append(int(str(N) + digit))
    return lst


print(max(insertion(-555)))

wondering if there is a more efficient solution for this problem.

Upvotes: 1

Views: 74

Answers (1)

blhsing
blhsing

Reputation: 106901

Your solution costs O(n ^ 2) in time complexity due to the repeated string slicing and joining per iteration over the length of the string.

To solve this in linear time (of O(n) time complexity), you can instead insert the given digit right before the first digit in the number that's smaller, or if the number is negative, perform the same search in reverse:

def insertion(N, digit):
    digits = str(abs(N))
    insert_at = 0
    for d in reversed(digits) if N < 0 else digits:
        if d < digit:
            break
        insert_at += 1
    if N < 0:
        insert_at = len(digits) - insert_at
    return ''.join((('-' if N < 0 else ''), digits[:insert_at], digit, digits[insert_at:]))

so that:

print(insertion(26, '3'))
print(insertion(821, '3'))
print(insertion(555, '3'))
print(insertion(-555, '3'))

outputs:

326
8321
5553
-3555

Upvotes: 1

Related Questions