given a number, find the minimum of all numbers formed by replacing any 2 consecutive digits with the higher of the 2

1
votes

Ex: If N = 8729, the numbers are 829, 879, 879. Minimum number is 829.

Brute force is finding the minimum of all the numbers formed by removing the lower digit of consecutive pairs. The time complexity is O(n). Is there a better way to think about this?

2
algorithmmath
I don't want to change the intent of your question, but it sounds like you want to rephrase your title to "Given a number N, find the smallest number in the set of numbers generated by replacing any two consecutive digits in N with the higher of the two". – LinuxDisciple
An equivalent set would be formed by dropping any digit that is adjacent to a larger digit. I think it's easier to think about it that way because instead of looking at each pair of consecutive numbers, you look at one digit and compare it to one or both neighbors. That way you can go sequentially and skip duplicates (like 879 879). – LinuxDisciple
What do you do for equal, consecutive digits? For 889, is the generated set [88, 89] or is it just [89]? – LinuxDisciple

2 Answers

0
votes

Brute force is finding the minimum of all the numbers formed by removing the lower digit of consecutive pairs. The time complexity is O(n).

It's very confusing what you meant exactly by O(n).

What is n? How is it related to N in your example (N = 8729)? Did you mean an algorithm that enumerates all possible options and selects the minimum value has O(N) run-time complexity?

If so, then I think you're probably wrong. The run-time complexity is O(log(N)) (the same for space complexity). The reason is the number of all possible options equal to the number of digits of N, which approximately equals to log10 of N.

I don't think you can get any better than this. Some prunings may improve average case complexity but the worst case is always O(log(N)).

0
votes

I do not believe that you can improve on O(N), where N is the number of digits in the number. However, I believe you can improve on the computation cost, since the term "minimum" implies left-to-right ordering.

Consider a number represented by ABC... where the "..." represents an arbitrary number of additional digits.

If A>B, then all possible solutions must begin with A. This can be seen in your example, where all possible solutions begin with 8. If A<=B, then possible solutions can begin with both A and B, but since A is lower, only those that start with A can possibly meet the criteria of minimum.

So, we know that the first digit will always represent the first digit in the answer!

Taking this a step further, if A<=B, the minimum solution will always be the solution to BC... prefixed with A. Consider 7829, where the minimum solution 789 is just 7 prefixed to the solution of 829.

But, if A>B, then B is optional in the minimum solution, allowing the choice - if B>C, then the minimum solution must be AC... by replacing AB=>A, since AB... would always be larger than AC..., short-cutting the solution as soon as this condition is met on any sub-solution.

Note that this is still O(N) due to the worst-case scenario for entirely ascending digits, but may eliminate some of the individual steps, which I believe is the best that can be done with this.