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

• @zhu8 there is still one problem, it should be in the order of larger mid and small, seems some has proposed this one

• @OVSS I think your solution is correct

• The idea is to count from right digit to left digit, as long as you can find the left digit is smaller than the right digit, then switch them will give the minimum number of the change.

``````class Solution(object):
def minReturnAfterChange(self, num):
reversed_digits = []
while num > 0:
residue = num % 10
num = num / 10
reversed_digits.append(residue)
for i in range(len(reversed_digits) - 1):
if reversed_digits[i] > reversed_digits[i + 1]:
reversed_digits[i + 1] = reversed_digits[i]
reversed_digits.__delitem__(i)
break

min_num = 0
reversed_digits.reverse()
for digit in reversed_digits:
min_num = min_num * 10 + digit
return min_num
``````

• @tczhaodachuan Good Solution!

• @pushazhiniao No. Stop at the first one like 23, where the first is smaller than the second.

• My Solution:

``````int removeAdj(int x){

string str = to_string(x);
int n = str.size();
if(n == 2)
return str[0] > str[1]? str[0] - '0' : str[1] - '0';

int replaced = -1;
for(int i = 0; i < n - 2; i++){
if(str[i] >= str[i+1] && str[i+1] > str[i+2]){
replaced = i;
break;
}
}

if(replaced == -1){
if(str[n-1] > str[n-2])
str[n-2] = str[n-1];
str.pop_back();
} else {
str = str.substr(0,replaced) + str.substr(replaced + 1,n-replaced-1);
}

return stoi(str);
}

``````

• @deshpana Thanks, if you can click thump up, the website may give me some points:)

• This should work. It's in Java.

``````public int solution2(int n) {
String s = String.valueOf(n);
int min = n;
int current;
for (int i = 0; i < s.length() - 1; i++) {
int max = Math.max(s.charAt(i), s.charAt(i+1)) - '0';
current = Integer.parseInt(s.substring(0,i) + max);
if (i < s.length() - 1) {
current = Integer.parseInt(current + s.substring(i+2));
}
if (current < min) {
min = current;
}
}
return min;
}
``````

• I came up with the solution using python:
Convert the number into string,
Traverse through the string and in each iteration compare two adjacent characters (digits) and replace the maximum of the two. Keep track of the minimum value.

``````def smallest(X):
'''
inType : integer
rType : integer
'''
x = str(X)
res = sys.maxsize
for i in range(len(x)-1):
s = x[0:i] + str(max(int(x[i]),int(x[i+1]))) + x[(i+2):len(x)]
if int(s) < res:
res = int(s)
return res
``````

• @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

are you sure about that? how about the last three digitals are the same, e.g. 000?

• Iterate from highest index, find the 3 length subsequence which meets high >= mid > low and replace the high digit and mid digit with high digit.
If there isn't any subsequence like this, replace the lowest two.
Example:
233614 -> can't find, replace 4 with 14
177763 -> 7 >= 7 > 6, replace 7 with 77
52231 -> can't find, replace 3 with 31
654321 -> 6 >= 5 >4, replace 65 with 6

any proof?

• @OVSS Is below the right implementation?

``````def replaceTwoAdjentDigits(num):
if num == 0:
return 0
nums = []
while num > 0:
digit = num % 10
nums.insert(0, digit)
num = num / 10
end = len(nums) - 1
mid = end - 1
start = end - 2
replaceStart = False
while start > 0:
if nums[start] >= nums[mid] and nums[mid] > nums[end]:
start -= 1
mid -= 1
end -= 1
else:
break
if start == 0:
replaceStart = True
break
if replaceStart:
larger = max(nums[start], nums[mid])
nums[start] = larger
nums[mid] = larger
nums.pop(start)
else:
larger = max(nums[end], nums[mid])
nums[end] = larger
nums[mid] = larger
nums.pop(mid)
minNum = 0
for num in nums:
minNum = minNum * 10 + num
return minNum
``````

• code in python, works fine

def smallest(a):
a = str(a)
a = list(a)
red = True
for i in range(len(a)-2):
if a[i]>=a[i+1]>a[i+2]:
a.remove(a[i+1])
print("".join(a))
red = False
break
elif red and i+1 == len(a)-2:
if max(a[len(a)-1],a[len(a)-2]) == a[len(a)-1]:
b = len(a)-2
else:
b = len(a)-1
a[b] = ""
print("".join(a))
break
smallest(756468)

• start iterating through digits from right to left. when u encounter a first instance when the number to ur immediate left is smaller to the current digit, replace both with the current digit. return.

If you end up reaching the leftmost digit, then go back to rightmost and second-rightmost digit and replace them with righmost digit. return

• Javascript. Naive approach. Non-efficient but it just work.

``````const solution = (x) => {
var ary = x.toString().split(''),
min = x
;
for (var i = 0; i < ary.length - 1; ++i) {
min = Math.min(
min,
parseInt(ary
.slice(0, i)
.concat([Math.max(parseInt(ary[i]), parseInt(ary[i + 1]))])
.concat(ary.slice(i + 2))
.join(""))
);
}

return min;
};
``````

• Python O(n) Solution:

``````def adjacentDigits(num):
l = map(int, str(num))
l.append(0)
min = num
for i in range(len(l)-2):
newl = l[:i] + [max(l[i],l[i+1])] + l[i+2:len(l)-1]
newl = map(str, newl)
x = int(''.join(newl))
if x < min:
min = x
return min``````

• ``````/**
Approach: Find the first descending triplet sequence (A[i] >= A[i+1] >= A[i+2]). In this triplet sequence, drop A[i + 1] so concatenate A[0:i] + A[i + 2].
If there's no descending triplet, simply repleace the last two digits in the sequence (A[A.length - 1] and A[A.length - 2]) with the larger
digit.
O(N) time. O(N) extra space for new string that's created at the end.
**/

public String replaceDups(String str){

int descStart = -1;
for(int i = 0; i + 2 < str.length(); i++){
if(str.charAt(i) >= str.charAt(i + 1) && str.charAt(i + 1) >= str.charAt(i + 2)){
descStart = i;
break;
}

}
if(descStart != -1){
return str.substring(0,descStart + 1) + str.substring(descStart + 2);
}
char max = str.charAt(str.length() - 2) >= str.charAt(str.length() - 1)? str.charAt(str.length() - 2): str.charAt(str.length() - 1);
return str.substring(0,str.length() - 2) + max;

}``````

• I want to point out that our number have at max about 10 digits, so be careful to not overthink and try to optimize the asymptotic run time, like this person trying to use maximum heaps. Show your interviewer that you don't blindly apply optimization without understanding the problem.

Here's a JavaScript one without converting to string (that feels like cheating): it's easy to read and it does the job

``````function solution(n) {
const arr = toArray(n);
let min = Infinity;
for (let i=0; i<arr.length-1; i++) {
const smaller = combine(arr, i);
min = Math.min(min, smaller);
}
return min;
}

function toArray(n) {
const arr = [];
while (n) {
arr.push(n % 10);
n = Math.floor(n / 10);
}
return arr.reverse();
}

function combine(arr, i) {
const smaller = arr.slice();
smaller.splice(arr[i] < arr[i+1] ? i : i+1, 1);
return +smaller.join('');
}

``````

• Here's my solution:

``````public class ReplaceTwoAdjacentDigitsWithLargerToFindSmallestNumberObtained {
public static void main(String[] args) {
System.out.println( " > " + obj.solution(233614));
}
/**
* 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);
*/
public int solution(int inputNumber) {
if (inputNumber < 10)
return inputNumber;
int minNumber = inputNumber;
String inputStr = inputNumber + "";
for(int i=0; i<inputStr.length() - 1; i++) {

char char1 = inputStr.charAt(i);
char char2 = inputStr.charAt(i+1);

String val = "";
if(char1 > char2) {
val = inputStr.substring(0,i+1) + inputStr.substring(i+2);
} else {
val = inputStr.substring(0,i) + inputStr.substring(i+1);
}

if(minNumber > Integer.parseInt(val.toString())) {
minNumber = Integer.parseInt(val.toString());
}
}
return minNumber;
}
}
``````

• ``````void finds(ulong num)
{
// eror check goes here.

// assume the number is min to begin with
ulong min = num;

string snum = num.ToString();
Console.WriteLine("snum is = " + snum);

for(int i=0; i<snum.Length-1; i++)
{
Console.WriteLine("snum chars" + Int16.Parse(snum[i].ToString()) + ".........." + Int16.Parse(snum[i+1].ToString()));
//int more = Math.Max(2,3);
int more = Math.Max(Int16.Parse(snum[i].ToString()),Int16.Parse(snum[i+1].ToString()));
Console.WriteLine("more = " + more);
Console.WriteLine("firstpart" + snum.Substring(0,i));
// Console.WriteLine("secondpart" + snum.Substring(i+2));
ulong newnum = Convert.ToUInt64(snum.Substring(0,i) +

more.ToString() +  snum.Substring(Math.Min(i+2,snum.Length)));
min = Math.Min(min,newnum);
}

Console.WriteLine(min);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.