[LeetCode] Minimum Factorization 最小因數分解

Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a.

If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.

Example 1

Input:

Output:

Example 2

這道題給了我們一個數字，讓我們進行因數分解，讓我們找出因數組成的最小的數字。從題目中的例子可以看出，分解出的因數一定是個位數字，即範圍是[2, 9]。那我們就可以從大到小開始找因數，首先查找9是否是因數，是要能整除a，就是其因數，如果是的話，就加入到結果res的開頭，a自除以9，我們用while循環查找9，直到取出所有的9，然後取8，7，6...以此類推，如果a能成功的被分解的話，最後a的值應該為1，如果a值大于1，說明無法被分解，傳回true。最後還要看我們結果res字元轉為整型是否越界，越界的話還是傳回0，參見代碼如下：

解法一：

<a>public:</a>

下面這種方法跟上面解法思路很像，隻是結果res沒有用字元串，而是直接用的長整型，我們每次在更新完res的結果後，判斷一次是否越整型的界，越了就直接傳回0，其他部分和上面沒有什麼差別，參見代碼如下：

解法二：

<a>class Solution {</a>

參考資料： 

<a href="https://discuss.leetcode.com/topic/92920/concise-c-solution-10-lines-3ms" target="_blank">https://discuss.leetcode.com/topic/92920/concise-c-solution-10-lines-3ms</a>

<a href="https://discuss.leetcode.com/topic/92998/c-clean-code-7-line-3-solutions/2" target="_blank">https://discuss.leetcode.com/topic/92998/c-clean-code-7-line-3-solutions/2</a>

，如需轉載請自行聯系原部落客。