Java solution with both Iterative and Recursive approach


  • 1
    C

    This is a very classic problem and it took me almost forever to understand the solution. There are more concise solution in this board but it was bit hard for me to understand them. IMO recursive approach is easier to understand and then it can be easily converted to iterative for better efficiency.

    For all those who on the same boat you may consider understanding the recursive approach then it will become easier to relate to the iterative approach

    Recursive:

    public int count_recursive(int num) {
    		// base case
    		if (num <= 0) {
    			return 0;
    		}
    
    		int constant = 0, position = 1, val = num;
    
    		while (val >= 10) {
    			position = position * 10;
    			val = val / 10;
    		}
    
    		if (val == 1) {
    			constant = num % position + 1;
    		}
    
    		else if (val > 1) {
    			constant = position;
    		}
    
    		// this is same as for input 254
    		// step 1 = 100 + 2(99) + (54)
    		// step 2 = 100 + 2( 10 + 9(9) + (9)) + (10 + 5(9) + (4))
    		// final step = 100 + 2( 10 + 9*1 + 1) + (10 + 5*1 + 1) since for number <= 9 will return 1
    		// result = 100 + 2 (20) + 16 = 156 ans
    		return constant + val * (count_recursive(position - 1)) + count_recursive(num % position);
    	}
    

    Converting the same approach to iterative

            /**
    	 * Performs two actions 
    	 * 1. computes occurrence in the lower digits 
    	 * 2. computes occurrence for the current digit
    	 * 		2a. if current digit == 1 then add seen so far // consider a small example like 234 and try it on a paper
    	 * 		2b. if current digit > 1 then add the full cycle i.e. if current digit power is 10^2 then add 10^2
    	 * e.g. if  input is 2346 and is current digit is 3 then 
    	 * position = 2 which represents there are two lower digits 
    	 * possition10PowerMinusOne = 10 which represents each lower digits contributes to 10
    	 */
    	public int count_iterative(int num) {
    		int seenNumbers = 0, count = 0, position = 0, position10Pow = 1;
    
    		while (num > 0) {
    			int lastDigit = num % 10;
    			
    			// used to know the power of lower digits
    			int position10PowMinusOne = position10Pow / 10;
    			
    			// if  input is 2346 and is current digit is 3 then 
    			// position = 2 which represents there are two lower digits 
    			// possition10PowerMinusOne = 10 which represents each lower digits contributes to 10
    			count += lastDigit * position * position10PowMinusOne;
    
    			if (lastDigit == 1) {
    				count += seenNumbers + 1;
    			} 
    			else if (lastDigit > 1) {
    				count += position10Pow;
    			}
    
    			seenNumbers = seenNumbers + (lastDigit * position10Pow);
    			position++;
    			position10Pow *= 10;
    			num /= 10;
    		}
    
    		return count;
    	}
    

Log in to reply
 

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