Easy-to-understand backtracking solution. Python and C++.


  • 0
    S

    Backtracking

    Assume a factorization is a series of m digits and the value represented by the first k-1 digits is called pre_val while the multiplication of the first k-1 digits is pre_mul. Then at the k^th step we need to choose another digit d from 2 to 9 (1 is useless). A non-zero digit d can be chosen if it satisfies that pre_mul*d can divide a. Then we test all such ds to get all possible factorization by backtracking. Finally, return the minimum one.

    Termination conditions

    • If pre_val is greater than the max signed integer

    • list itemIf pre_mul=a and pre_val can fit into a signed integer, i.e., we have found a legal solution.

    • list itemIf there exists no such d to make pre_mul*d a factor of a

    class Solution(object):
        def smallestFactorization(self, a):
            """
            :type a: int
            :rtype: int
            """
            if a < 10:
                return a
            self.a = a
            self.solutions = []
            self.backtrack(0, 1)
            return min(self.solutions) if self.solutions else 0
            
        def backtrack(self, pre_val, pre_mul):
            # check termination condition
            if pre_val > 2**31 - 1:
                return 
            if pre_mul == self.a:
                self.solutions.append(pre_val)
                return
            # choose the next digit
            for d in range(2, 10):
                current_mul = pre_mul * d
                if self.a % current_mul == 0:
                    current_val = pre_val * 10 + d
                    self.backtrack(current_val, current_mul)
            
    

    However, due to the insufficiency of recursion on LeetCode, this backtracking will lead to TLE. (I have encountered TLE multiple times when using backtracking in Python. Simply translate it into C++ and it will be accepted.)

    Then we rewrite the program in C++ and it is accepted with 403ms.

    #include <limits>
    class Solution {
    public:
    	int smallestFactorization(int a) {
    		if (a < 10)
    			return a;
    		std::vector<int> solutions;
    		backtrack(0, 1, solutions, a);
    		if (solutions.empty())
    			return 0;
    		else
    			return *std::min_element(solutions.cbegin(), solutions.cend());
    
    	}
    
    	void backtrack(long long pre_val, long long pre_mul, std::vector<int>& solutions, int a) {
    		// check termination conditions
    		if (pre_val > std::numeric_limits<int>::max())
    			return;
    		if (pre_mul == a) {
    			solutions.push_back((int)pre_val);
    			return;
    		}	
    		// choose the next digit
    		for (int d = 2; d < 10; d++) {
    			auto current_mul = pre_mul * d;
    			if (a % current_mul == 0) {
    				auto current_val = pre_val * 10 + d;
    				backtrack(current_val, current_mul, solutions, a);
    			}
    		}
    	}
    };
    

    Now we try to improve the above Python backtracking algorithm to avoid TLE. It is noted that at each step we should choose a digit d not less than the previous digit since we want to find the minimum solution. For example, ``48can be factorized into68and86and we will just keep68```. That is to say, each factorization series is still legal after random permutation and we keep the one whose digits appear in ascending order.

    With this improvement, the Python backtracking also passes the tests with only 99 ms.

    class Solution(object):
        def smallestFactorization(self, a):
            """
            :type a: int
            :rtype: int
            """
            if a < 10:
                return a
            self.a = a
            self.solutions = []
            self.backtrack(0, 1, 2)
            return min(self.solutions) if self.solutions else 0
            
        def backtrack(self, pre_val, pre_mul, pre_d):
            # check termination condition
            if pre_val > 2**31 - 1:
                return 
            if pre_mul == self.a:
                self.solutions.append(pre_val)
                return
            # choose the next digit
            for d in range(pre_d, 10):
                current_mul = pre_mul * d
                if self.a % current_mul == 0:
                    current_val = pre_val * 10 + d
                    self.backtrack(current_val, current_mul, d)
    

    I have also provided a dynamic programming solution at dynamic programming solution.


Log in to reply
 

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