Java code, pure Math, with detailed explanation


  • 0
    A
    public class Solution {
        public int smallestFactorization(int a) {
            // algorithm 2017/06/19: this is a math problem. Since the question is asking for each digit, we will need to make sure the prime factors can only be 2,3,5,7
            // and then can be factored into digits: 2,3,5,7, 4,6,8,9
            // key is the make sure the NUMBER of digits are the smallest. Once we get all the digits, we sort them and get the result
    
            // the following algo does not work with the case that 1==a
            if (1 == a) {
                return 1;
            }
    
            int count2s = 0, count3s = 0, count5s = 0, count7s = 0;
            while (0 == a % 7) {
                count7s++;
                a /= 7;
            }
            while (0 == a % 5) {
                count5s++;
                a /= 5;
            }
            while (0 == a % 3) {
                count3s++;
                a /= 3;
            }
            while (0 == a % 2) {
                count2s++;
                a /= 2;
            }
            if (1 != a) {
                return 0;   // a has prime factors larger than 7
            }
    
            // 5, 7 cannot be multiplied with 2 or 3 to reach a single digit
            // so the only choices are 2, 3, 2*2, 2*3, 2*2*2, 3*3
            // to reach a 'smallest' positive, we must reduce the number of digits
            // example 2 2 2 3 3 => 89, is better than => 249
            // therefore, for 2s, we must always find three 2s and combine them into single digit 8
            // that gives us three possibilities: 3n 2s, 3n+1 3s, 3n+2 2s
    
            // if there are 3n 2s, then we simply combine every 2 3s to be a 9, so the final digits are:
            //   zero 2,  2m   3s => 9s
            //   zero 2,  2m+1 3s => 3, 9s
    
            // if there are 3n+1 2s, or 3n+2 2s, then we need to combine the 2s and 3s to get the smallest NUMBER of digits
    
            // if there are 3n+1 2s, the single 2 can be combined with 3s with the following rule:
            //   single 2,  2m 3s   => 2, 9s (NUMBER of digits is m+1)
            //   single 2,  2m+1 3s => 6, 9s (NUMBER of digits is m+1)
    
            // if there are 3n+2 2s, the two 2s can be combined with 3s with the following rule:
            //   double 2s, 2m 3s   => 4, 9s (NUMBER of digits is m+1)
            //   double 2s, 2m+1 3s => 2, 6, 9s
    
            int count2sInResult = 0;
            int count3sInResult = 0;
            int count4sInResult = 0;
            int count5sInResult = count5s;
            int count6sInResult = 0;
            int count7sInResult = count7s;
            int count8sInResult = 0;
            int count9sInResult = 0;
    
            count8sInResult = count2s / 3;      // 2X2X2 = 8
            count9sInResult = count3s / 2;      // 3X3 = 9
            // remaining unused 2s and 3s
            count2s         = count2s % 3;      // 0, 1, 2
            count3s         = count3s % 2;      // 0, 1
    
            if (0 == count2s) {
                // remaining 3: either zero (if even number of 3s, all converted into 9), or one
                count3sInResult = count3s;
            } else if (1 == count2s) {
                if (0 == count3s) {
                    count2sInResult = 1;    // 2 9..9
                } else {
                    count6sInResult = 1;    // 6 9..9
                }
            } else {    // 2 == count2s
                if (0 == count3s) {
                    count4sInResult = 1;    // 4 9...9
                } else {
                    count2sInResult = 1;    // 2 6 9...9
                    count6sInResult = 1;
                }
            }
    
            StringBuilder builder = new StringBuilder();
            for (int index = 0; index < count2sInResult; index++) {
                builder.append(2);
            }
            for (int index = 0; index < count3sInResult; index++) {
                builder.append(3);
            }
            for (int index = 0; index < count4sInResult; index++) {
                builder.append(4);
            }
            for (int index = 0; index < count5sInResult; index++) {
                builder.append(5);
            }
            for (int index = 0; index < count6sInResult; index++) {
                builder.append(6);
            }
            for (int index = 0; index < count7sInResult; index++) {
                builder.append(7);
            }
            for (int index = 0; index < count8sInResult; index++) {
                builder.append(8);
            }
            for (int index = 0; index < count9sInResult; index++) {
                builder.append(9);
            }
    
            // overflow?
            int result = 0;
            try {
                result = Integer.parseInt(builder.toString());
            } catch (Exception ex) {
                // overflow
                result = 0;
            }
            return result;
        }
    }

Log in to reply
 

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