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


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

    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

  • 0
    D
    /**
    	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('');
    }
    
    

Log in to reply