# Replace two adjacent digits with larger one to find the smallest number that can be obtained

• You are given an integer X. You must choose two adjacent digits and replace them with the larger of these two digits.

For example, from the integer X = 233614, you can obtain:
33614 (by replacing 23 with 3);
23614 (by replacing 33 with 3 or 36 with 6);
23364 (by replacing 61 with 6 or 14 with 4);

You want to find the smallest number that can be obtained from X by replacing two adjacent digits with the larger of the two. In the above example, the smallest such number is 23364.

Write a function:

``````class Solution {public int solution (int X);}
``````

that, given a positive integer X, returns the smallest number that can be obtained from X by replacing two adjacent digits with the larger of the two.

For example, given X = 233614, the function should return 23364, as explained above.

Assume that:

``````X is an integer within the range [10..1,000,000,000].
``````

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

• Had no clue how to do this. I believe I ended up converting them to strings and compare the individual characters, which is so damned dumb lol. I'm curious how would everyone else solve this?

• I haven't figure out the best way yet. But there's one thing for sure that we should skip the ascent sequence front MSB, the reason is trivial.

• I tried with this one

``````
def smallestNumber(num):
digits = [int(i) for i in str(num)]
l = len(digits) - 1
if (len(digits) == 2):
return max(digits[0], digits[l])
else:
if digits[l - 2] > digits[l - 1]  and digits[l - 1]  > digits[l] :
digits[l - 1]  = digits[l]
else:
digits[l - 1] = max(digits[l - 1], digits[l])
return reduce(lambda x, y: 10 * x + y, digits[0:l], 0)``````

• Go through all the replacement and keep track of the min one.

• Is my thought too simple? Here is what I think:

By replacing two digit a,b with one digit X, in anyway the number gets smaller.
As x = max(a,b), so the number always gets larger than keep "a" at its position. So try to avoid replacing at the most significant part.
All this leaves us only 1 choice, that is replacing the last two digits... the impact is only max(a,b) - min(a,b) comparing with other (max(a,b) - min(a, b)) * 10^?

• @henryly94 The question says to focus on correctness than performance. So probably a brute force is good enough.

• @cau-seoi-dyun-dou we should prove that we only need last 3 digits to find a solution. I think that it is very easy to prove it and will leave it to yourself

• @cau-seoi-dyun-dou I understand, just some little thought

• I have a Ruby implementation:

``````str = "233614"

def smaller_number(str)
smaller = nil
for i in 0 ... str.size
new_str = str.dup

if i == (str.size - 1)
break
end

max = [new_str[i].to_i, new_str[i+1].to_i].max

if max == new_str[i]
new_str[i+1] = ''
else
new_str[i] = ''
end

if smaller.nil?
smaller = new_str.to_i
else
if smaller > new_str.to_i
puts "#{smaller} > #{new_str}"
smaller = new_str.to_i
else
puts "#{smaller} < #{new_str}"
smaller = new_str.to_i
end
end
end

puts smaller
end

smaller_number(str)
``````

Is this dumb?

• Here's the idea, start from the rightmost index towards left and keep moving till the current element(ith index) is less than the previous element(i+1th index). If it is greater than the previous element then,remove the i+1 element and return.
If the number keeps on increasing from left to right then remove the element at index 1.

• We can utilize Heap or Priority queue in this case. Java solution is as below -

``````public int obtainSmallest(int num){

String strNum = String.valueOf(num);
PriorityQueue<Integer> queue = new PriorityQueue<>();

for(int i=0; i<strNum.length()-1; i++){
String newString = i == 0 ? "" : strNum.substring(0,i);
if(strNum.charAt(i) > strNum.charAt(i+1)){
newString += strNum.charAt(i) + strNum.substring(i+2, strNum.length());
}else{
newString += strNum.charAt(i+1) + strNum.substring(i+2, strNum.length());
}
}

return queue.poll();

}
``````

• @elmirap Your solution is wrong.

EX: input 177763. Your solution gives 17773. But if you combine any of the two 7's you get 17763.

17763 < 17773

• Here's my approach-

• Find the first non-increasing sequence from the left of size > 2 and replace the first 2 digits of this sequence.
• Else, replace the last 2 digits.

• @elmirap how abaout 654321, we need to remove 5 here

• @tyasink yes, seems there is a flaw in algorithm

• Here's the idea, start from the rightmost index towards left and keep moving till the current element(ith index) is less than the previous element(i+1th index). If it is less than the previous element then,remove the current(i) element and return.
If the number keeps on increasing from left to right then remove the element at index 1.

• @deshpana What is the use of a PriorityQueue here ?
We can just maintain a single variable to track the current minimum.

• If I understand your algorithm correctly, there are some cases that fail

Here's the idea, start from the rightmost index towards left and keep moving till the current element(ith index) is less than the previous element(i+1th index). If it is greater than the previous element then,remove the i+1 element and return.

sample input: 2321