sample dp solution


  • 0
    T
    public class Solution {
        public int SmallestFactorization(int a) {
            if(a < 10)
                return a;
            int[] dp = new int[10];
            
            while(a > 1){
                if(a % 2 == 0){
                    a/=2;
                    dp[2]++;
                }else if(a % 3 == 0){
                    a/=3;
                    dp[3]++;
                }else if(a % 5 == 0){
                    a/=5;
                    dp[5]++;
                }else if(a % 7 == 0){
                    a/=7;
                    dp[7]++;
                }else{
                    break;
                }
            }
            
            if(a > 10){
                return 0;
            }
            
            dp[8] = dp[2]/3;
            dp[2] %= 3;
            
            dp[9] = dp[3]/2;
            dp[3] %= 2;
            
            dp[6] = Math.Min(dp[2],dp[3]);
            dp[2] -= dp[6];
            dp[3] -= dp[6];
            
            dp[4] = dp[2]/2;
            dp[2] = dp[2]%2;
            
            long result = 0;
            
            for(int i = 2;i<=9 && result <= int.MaxValue;i++){
                for(int j = 0;j<dp[i] && result <= int.MaxValue;j++){
                    result = result *10 + i;
                }
            }
            
            if(result > int.MaxValue)
                result = 0;
                
            return (int)result;
        }
    }
    

Log in to reply
 

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