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


  • 0
    Z

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


  • 0
    Z

    @OVSS I think your solution is correct


  • 0
    T

    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
    

  • 0
    D

    @tczhaodachuan Good Solution!


  • 0
    S

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


  • 0
    J

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

  • 0
    T

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


  • 0

    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;
    	}
    

  • 0
    P

    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
    

  • 0
    U

    @elmirap said in Replace two adjacent digits with larger one to find the smallest number that can be obtained:

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


  • 0
    U

    @OVSS said in Replace two adjacent digits with larger one to find the smallest number that can be obtained:

    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?


  • 0
    T

    @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
    

  • 0
    H

    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)


  • 0
    D

    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


  • 0
    P

    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;
    };
    

  • 0
    S

    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

  • 1
    /**
    	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;
    
    }

  • 0
    F

    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('');
    }
    
    

  • 0
    K

    Here's my solution:

    public class ReplaceTwoAdjacentDigitsWithLargerToFindSmallestNumberObtained {
        public static void main(String[] args) {
            ReplaceTwoAdjacentDigitsWithLargerToFindSmallestNumberObtained obj = 
                    new ReplaceTwoAdjacentDigitsWithLargerToFindSmallestNumberObtained();
                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;
        }
    }
    

  • 0
    A
    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);
        }
    

Log in to reply
 

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