Efficient algorithm to get the largest possible number by inserting a single digit

Question

I have just written the algorithm below to get the largest possible number by inserting any specific number.

getLargestPossible receives two arguments and aims at finding the maximum possible number by inserting numInsertion into any position in num. As an example:

getLargestPossible(623, 5) and getLargestPossible(-482, 5) returns 6523 and -4582, respectively.

How could I write this algorithm in the most effective way?

def attachRest(list_int, str_num, index):
    '''
    Converts list_int to list of strings, merges it with str_num 
    (splitted from index) and returns the result as an integer
    '''
    s = [str(i) for i in list_int]
    str_num = str_num[index:]
    s = s + list(str_num)
    num = int("".join(s))
    return num

def getLargestPossible(num, numInsertion):
    '''
    Returns a largest possible number by inserting numInsertion into num
    e.g.: getLargestPossible(623, 5)  returns 6523
          getLargestPossible(-482, 5) returns -4582
    '''
    new_num = []
    isNumberInserted = False
    
    if num > 0:
        str_num = str(num)
        for index, digit in enumerate(str_num):
            if numInsertion > int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
            
        if isNumberInserted is False: #e.g. if num==666 and numInsertion==5, return 6665
            num = num * 10 + numInsertion
            
        print(num)
    else:
        str_num = str(-1 * num)
        for index, digit in enumerate(str_num):
            if numInsertion < int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
    
        if isNumberInserted is False:
            num = num*10 - numInsertion
            print(num)
        else:
            print(-1 * num)

Answer 1

Can't you simplify to something like this:

def get_largest_insertion(long_n,n):
    sn=str(abs(long_n))
    n=str(n)
    sign='-' if long_n<0 else '+'
    return(max(int(sign+sn[0:i]+n+sn[i:]) for i in range(len(sn)+1)))


>>> get_largest_insertion(623, 5)
6523
>>> get_largest_insertion(-482,5)
-4582
>>> get_largest_insertion(666,5)
6665

OK, let's make it faster

With simple inspection, I believe it is true that if the number is negative, the insertion will always be one of:

1. End of the string (such as f(-524242, 8): -5242428); OR
2. Left of the first larger digit (such as f(-3251342,2): -23251342 or f(-1251342,2): -12251342

And for a positive number:

1. End of the string (such as f(345342,2): 3453422); OR
2. Left of the first smaller digit (such as f(3251342,2): 32521342

You can modify my function so that it finds that insertion point in one go with:

def f3(long_n, n):
    sn=str(abs(long_n))
    sign='-' if long_n<0 else '+'
    n=str(n)
    if sign=='-':
        i=next((i for i,c in enumerate(sn) if c>n), len(sn))
    else:
        i=next((i for i,c in enumerate(sn) if c<n), len(sn))

    return int(sign+sn[0:i]+n+sn[i:])   

Now let's benchmark with this:

# your original function is f1
# my original is f2
# new one is f3

import time

# ====================
def attachRest(list_int, str_num, index):
    s = [str(i) for i in list_int]
    str_num = str_num[index:]
    s = s + list(str_num)
    num = int("".join(s))
    return num

def f1(num, numInsertion):
    new_num = []
    isNumberInserted = False
    
    if num > 0:
        str_num = str(num)
        for index, digit in enumerate(str_num):
            if numInsertion > int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
                
        if isNumberInserted is False:
            num = num * 10 + numInsertion
            
        return num
    else:
        str_num = str(-1 * num)
        for index, digit in enumerate(str_num):
            if numInsertion < int(digit):
                new_num.append(numInsertion)
                num = attachRest(new_num, str_num, index)
                isNumberInserted = True
                break
            else:
                new_num.append(int(digit))
                
        if isNumberInserted is False:
            num = num*10 - numInsertion
            return num
        else:
            return -1 * num

# ===============
        

def f2(long_n,n):
    sn=str(abs(long_n))
    n=str(n)
    sign='-' if long_n<0 else '+'
    return(max([int(sign+sn[0:i]+n+sn[i:]) for i in range(len(sn)+1)]))

def f3(long_n, n):
    sn=str(abs(long_n))
    sign='-' if long_n<0 else '+'
    n=str(n)
    if sign=='-':
        i=next((i for i,c in enumerate(sn) if c>n), len(sn))
    else:
        i=next((i for i,c in enumerate(sn) if c<n), len(sn))

    return int(sign+sn[0:i]+n+sn[i:])       
            
# =====
def cmpthese(funcs, args=(), cnt=100, rate=True, micro=True, deepcopy=True):
    from copy import deepcopy 
    """Generate a Perl style function benchmark"""                   
    def pprint_table(table):
        """Perl style table output"""
        def format_field(field, fmt='{:,.0f}'):
            if type(field) is str: return field
            if type(field) is tuple: return field[1].format(field[0])
            return fmt.format(field)     
        
        def get_max_col_w(table, index):
            return max([len(format_field(row[index])) for row in table])         
        
        col_paddings=[get_max_col_w(table, i) for i in range(len(table[0]))]
        for i,row in enumerate(table):
            # left col
            row_tab=[row[0].ljust(col_paddings[0])]
            # rest of the cols
            row_tab+=[format_field(row[j]).rjust(col_paddings[j]) for j in range(1,len(row))]
            print(' '.join(row_tab))                
            
    results={}
    for i in range(cnt):
        for f in funcs:
            if args:
                local_args=deepcopy(args)
                start=time.perf_counter_ns()
                f(*local_args)
                stop=time.perf_counter_ns()
            results.setdefault(f.__name__, []).append(stop-start)
    results={k:float(sum(v))/len(v) for k,v in results.items()}     
    fastest=sorted(results,key=results.get, reverse=True)
    table=[['']]
    if rate: table[0].append('rate/sec')
    if micro: table[0].append('\u03bcsec/pass')
    table[0].extend(fastest)
    for e in fastest:
        tmp=[e]
        if rate:
            tmp.append('{:,}'.format(int(round(float(cnt)*1000000.0/results[e]))))
            
        if micro:
            tmp.append('{:,.1f}'.format(results[e]/float(cnt)))
            
        for x in fastest:
            if x==e: tmp.append('--')
            else: tmp.append('{:.1%}'.format((results[x]-results[e])/results[e]))
        table.append(tmp) 
    
    pprint_table(table)  


if __name__=='__main__':
    import sys
    import time 
    print(sys.version)

    funcs=[f1, f2, f3]
    
    cases=(
        (-524242,8),
        (345342,2),
        (-34734573524242,8),
        (71347345345342, 2)
    )
    for ln, n in cases:
        for f in funcs:
            print(f'{f.__name__}{ln, n}: {f(ln,n)}')
        args=(ln, n)
        cmpthese(funcs,args)    
        print()

That benchmark prints:

3.9.0 (default, Nov 21 2020, 14:55:42) 
[Clang 12.0.0 (clang-1200.0.32.27)]
f1(-524242, 8): -5242428
f2(-524242, 8): -5242428
f3(-524242, 8): -5242428
   rate/sec μsec/pass     f2     f1     f3
f2   19,777      50.6     -- -37.0% -57.1%
f1   31,402      31.8  58.8%     -- -32.0%
f3   46,148      21.7 133.3%  47.0%     --

f1(345342, 2): 3453422
f2(345342, 2): 3453422
f3(345342, 2): 3453422
   rate/sec μsec/pass     f2     f1     f3
f2   19,671      50.8     -- -38.4% -56.5%
f1   31,916      31.3  62.2%     -- -29.5%
f3   45,260      22.1 130.1%  41.8%     --

f1(-34734573524242, 8): -347345735242428
f2(-34734573524242, 8): -347345735242428
f3(-34734573524242, 8): -347345735242428
   rate/sec μsec/pass     f2     f1     f3
f2   10,331      96.8     -- -38.1% -72.6%
f1   16,689      59.9  61.5%     -- -55.7%
f3   37,679      26.5 264.7% 125.8%     --

f1(71347345345342, 2): 721347345345342
f2(71347345345342, 2): 721347345345342
f3(71347345345342, 2): 721347345345342
   rate/sec μsec/pass     f2     f1     f3
f2   10,579      94.5     -- -67.7% -77.4%
f1   32,779      30.5 209.8%     -- -29.9%
f3   46,743      21.4 341.8%  42.6%     --

So same approach but inspection vs brute force makes it 2x to 3x faster...