6-liner C++ & Python (find largest under 10 divider recursively)


  • 0

    Just recursively find largest under 10 divider d from a, and form these dividers from lower to higher significant positions, which will yield to the result.

    NOTE: Do not re-test those larger digits which failed to be a divider before.

        int smallestFactorization(int a) {
           int res = (a==1);
           for (int m = 1, d = 9; a > 1; m *= 10, a /= d) {
               while (d > 1 && a%d) --d; // find largest divider under 10
               if (d == 1 || d > INT_MAX/m || res > INT_MAX-d*m) return 0; // check for overflow
               res += d*m;
           }
           return res;
        }
    

    Python:

        def smallestFactorization(self, a):
            val = '' if a > 1 else '1'
            while a > 1:
                for i in range(9,1,-1):
                    if not a%i:
                        a /= i
                        val += str(i)
                        break
                else: return 0
            val = int(val[::-1])
            return val if val <= 2**31 else 0
    

Log in to reply
 

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