Simple Recursive Java Solution With Explanation


  • 0
    S

    I used a simple recursive solution. After writing out many different numbers and tracing through each solution, you notice that you want to find the first digit that is greater than the digit to its right, decrease it by 1 and set the remaining digits to 9. The problem is that sometimes you have numbers for which this technique doesn't work.

    Ex: 332 => 329, which isn't monotone increasing.

    So I took a recursive approach. Each recursion, see if the number is monotone by looping through it once. If it is, return the solution. If not, find the first digit which is greater than digit to its right, decrease it by 1, and set remaining digit to 9. Then you recursively call the function again.

    Note: It is O(n) per recursive call, so maybe I can consider a better approach, but seems to work for me and passes all the test cases :)

    class Solution {
        public int monotoneIncreasingDigits(int N) {
            char[] num = Integer.toString(N).toCharArray();
            calculateString(num);
            return Integer.parseInt(new String(num));
        }
        
        public String calculateString(char[] num){
    
            boolean flag = false;
            int index = -1;
            for(int i = 0; i < num.length - 1; i++){
                if(num[i] > num[i+1]){
                    flag = true;
                    num[i]--;
                    index = i + 1;
                    break;
                }
            }
            
            if(!flag){
                return num.toString();
            }
            
            while(index < num.length){
                num[index++] = '9';
            }
            
            return calculateString(num);
        }
    }
    

    Thanks @khaled_acmilan for helping me provide a cleaner solution! :)


  • 0
    K

    Thank you for sharing your solution , you can optimize it by doing the following :

          public  int MonotoneIncreasingDigits(int N) {
    
    		    char[] number = N.ToString().ToCharArray();
                       calculateString(number);
                       return int.Parse(new string(number));
    	}
    
        private  string calculateString(char [] number) {
    		
            bool check = false;
            int index = -1;
            for (int i = 0; i < number.Length - 1; i++)  {
               
                   if(number[i] > number[i+1])
                   {
                        number[i]--;
                        check = true;
                        index = i + 1;
                        break;
                   }
            }
    
            if (!check) return number.ToString();
    
            while (index < number.Length)
                number[index++] = '9';
    
            return calculateString(number);
    
    }

  • 0
    S

    @khaled_acmilan Absolutely! Thanks for pointing that out! I will update my solution now.


Log in to reply
 

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