Find the smallest number greater than "n" with the same digit sum as "n"

Question

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))

enter image description here

As you can see, even with a not-so-huge input as 70 million, the code takes ~1.5 mins to run.

Answer 1

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.

1. 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) -> 132
2. 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.
3. 129993 - here we have a similar case as #2. The only difference is that the full 999 must go to the end -> 132999.
4. 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 >= 0:
 if int(n[i]) != 0:
 break
 trailing_zeros.append(n[i])
 i -= 1
 if i < 0:
 print ("No solution!")
 return
 first_non_zero_digit = int(n[i])
 i -= 1
 while i >= 0:
 if int(n[i]) != 9:
 break
 first_nines.append(n[i])
 i -= 1
 if i < 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))

• Oscar Smith: I new I was missing something. Thanks for finding it!
• Anatolii: @OscarSmith I also added a quick implementation of the approach, Maybe it will be also useful :)

Answer 2

This is a case where your algorithm needs help. There are 3 cases to consider: only 1 nonzero digit, 1 less than a power of 10, and everything else.

1. a*10^n goes to 10^(n+1)+(a-1)
2. 10^n - 1 goes to 10^n + 10^n - 10^(n-1)
3. Otherwise, increase the 2nd least significant non-zero by 1, and decrease the last nonzero by 1.

This algorithm will run in linear time to the number of digits in n (as opposed to yours which is exponential).

• stefan: your algorithm is not sufficient. 101 shall be 110 not 200.

Answer 3

Algorithm

Yout code searches all numbers and test for the sum. That is inefficient.

The result consists from left to right of

• 0 or more digits from the original input
• exactly one digit that is incremented (could be a leading zero incremented to one)
• the minimal representation of the remaining sum r filling the remaining digits which is from right to left
  • r//9 '9's
  • one digit r%9 (only if greater 0)
  • 0 or more leading '0's to fill the gap