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


  • 11
    R

    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.


  • 1

    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?


  • 1
    H

    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.


  • 0

    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)

  • 0
    P

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


  • 3
    O

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


  • 1
    C

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


  • 0

    @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


  • 0
    H

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


  • 0
    R

    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?


  • 2
    M

    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.


  • 2
    D

    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());
    			}
    			queue.add(Integer.valueOf(newString));
    		}
    		
    		return queue.poll();
    		
    	}
    

  • 0
    J

    @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


  • 10
    V

    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.

  • 0
    T

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


  • 0

    @tyasink yes, seems there is a flaw in algorithm


  • 0
    T

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

    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.

    how about 121 or 2321


  • 0
    A

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


  • 0
    M

    @tyasink made the changes.


  • 2
    T

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

    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
    your solution: 232
    correct solution: 231

    If the number keeps on increasing from left to right then remove the element at index 1.

    sample input: 1234
    your solution: 134
    correct solution: 124


Log in to reply
 

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