CODEWITHSUNDEEP
pythonperformancemath
Psychicplatypus
Psychicplatypus

Reputation: 25

Reducing time complexity for Python, finding numbers with same digits

I'm writing code that returns the next bigger number with the same digits. I thought that my solution was pretty fast, but when testing it I've realized that my time complexity is really bad.

def next_bigger(n):
    j = n
    for i in range(n):
        n+=1
        if sorted(str(j)) == sorted(str(n)):
            return n
    return -1

print(next_bigger(143255555555555553223))

Is there a faster way of implementing this algorithm. Is there a way for me to replace sorted() and remove the for loop?

Note: if it can't find a bigger number it returns -1. Forgot to add, thought it was clear.

Note 2: Sorry, I'm bad at writing questions. The original algorithm had while True instead of a for loop. That's why it returns -1 when running it as is, having while True will give the correct answer but it will take time.

Some inputs: 123 -> 132 || 2532 -> 3225 || 543890432 -> 543892034 || 143255555555555553223 -> 143255555555555553232 ||

Upvotes: 0

Views: 163

Answers (1)

Nathaniel Ford
Nathaniel Ford

Reputation: 21220

You fundamental problem is that you're starting with the most significant digit and working forward from there, when you want to start with your least significant digit and find the least other significant digit that it can replace.

Thus: if you have the number 432, the 2 wants to swap with the 3 so as to create 423, the next smallest number with the same digits. That means, starting at the smallest number you want to look at each increasing digit in increasing significance order. (In the above example, first at 3 then at 4). The first digit that the least significant digit is smaller than, it should replace. Finally, if there are no numbers that are bigger than it (i.e. 419 - the 9 is the largest digit), you should try again, but starting at the second to last number, and so on. Only if you exhaust all digits in this manner should you return a false value.

At best this approach gives an O(len(n)^2) time, though, since it requires a double iteration (for each digit, starting at the last and moving forward, check each digit starting at the second to last and move forward). There might be a better way I'm not thinking of.

There are edge cases to handle (what if you n is 0 or 1 length? What happens with the number 100?), but this is the core of what you're going for:

for alpha in range(len(n), -1, -1):
    alpha_num = n[alpha]
    for omega in range(len(n-1), -1, -1):
        omega_num = n[omega]
        if alpha_num < omega_num:
            n[omega] = alpha_num
            n[alpha] = omega_num
            return n

Addendum: Next largest number

Based on comments made, I suspect I misinterpreted the goal. It is not that you want to find some number b that is strictly less than a and utilizes all the same digits, as well as being the largest of all such numbers, but rather you want to find a b that is strictly larger than a and also uses all the same digits and is the smallest of all such numbers.

Thus you might have these examples:

432 -> No result
567 -> 576
627 -> 672
587 -> 758
672 -> 726

You're going to want to utilize a similar approach, starting with your least significant digits and working to the left to find the smallest number that is still larger and swap. This doesn't cover all the cases though. (I'll return to this when I have more than a minute to write out the algorithm, but maybe this helps set you in the right direction.)

Upvotes: 1

Related Questions