Find the smallest number greater than "n" with the same digit sum as "n" Here is my code:

def func(n):
    sum_digits_n = 0
    for i in str(n):
        sum_digits_n+=int(i)

    num = n+1

    while True:
        s = 0
        for i in str(num):
            s+=int(i)
        if s==sum_digits_n:
            return num
            break
        else:
            num += 1


It works for small to moderate sized n. But it takes forever to run with big values of n. How can I optimize it?



For example, let's check the run times for different sized inputs:

import time
inputs = [7,70,700,7000,70000,700000,7000000,70000000]
for i in inputs:
    t = time.time()
    ans = func(i)
    print('Input: {}. Ans: {}. Time taken: {}s\n'.format(i, ans, time.time()-t))




As you can see, even with a not-so-huge input as 70 million, the code takes ~1.5 mins to run.
You have to come up with a trickier algorithm here rather than doing a brute force approach. 

Let's try to think about a couple of cases here.


123, its sum of digits is 6. If we decrease 3 by 1, then we'll have to increase 2 by 1 (as you're trying to get the least larger element) -&gt; 132 
1293, sum of digits is 15. If we decrement 3 and increment 2 (9 is already a maximum digit so we cannot increment it) then we'll get 1392. But is it really the least greater value? Well, no, 1329 is. So, what we should do it increment 2, substitute 9 with 3 and decrement 3 (as 2 was just incremented). 9 must go to the end to minimise the value as much as possible.
129993 - here we have a similar case as #2. The only difference is that the full 999 must go to the end -&gt; 132999.
12920 - another interesting case. But again, find the first non-zero digit from the left, then if 9s are its immediate neighbours move them to  the end, decrement 2 and put 0 before it -> 13019.


Hopefully, based on examples above it's clear which steps have to be implemented (we move from right to left):


Find the rightmost digit that can be decremented. So, 0 cannot be such a digit as it's minimal already. If such digit doesn't exist then there's no solution. Decrement it.
Find the closest digit to the left of the digit from step 1 that can be incremented. So, 9 cannot be such a digit as it's maximum already. If there's no such digit then just prepend 0 to the start of the current number. Increment the digit.
Now, sort all the digits after the digit from step 2 in ascending order.
You have a solution now!


UPDATE

As a bonus, a quick implementation of the approach in Python. I'll leave it up to you to improve this solution (if possible :) )

def solve(n):
    size = len(n)

    trailing_zeros = list()
    first_nines = list()

    i = size - 1
    while i &gt;= 0:
        if int(n[i]) != 0:
            break
        trailing_zeros.append(n[i])
        i -= 1

    if i &lt; 0:
        print ("No solution!")
        return

    first_non_zero_digit = int(n[i])
    i -= 1
    while i &gt;= 0:
        if int(n[i]) != 9:
            break
        first_nines.append(n[i])
        i -= 1

    if i &lt; 0:
        remaining = '1'
    else:
        increased_digit = int(n[i]) + 1
        remaining = ''.join(n[:i]) + str(increased_digit)

    print(remaining + ''.join(trailing_zeros) + str(first_non_zero_digit - 1) + ''.join(first_nines))