找出最小的整數，其數字的平方和添加到給定數量

Question

例子：

輸入：|輸出：

• 5 - > 12（1^2 + 2^2 = 5）

• 500 - > 18888999（1^2 + 8^2 + 8^2 + 8^2 + 9^2 + 9^2 + 9^2 = 500）

我寫了一個非常簡單的蠻力解決方案，但是它有很大的性能問題：

#include <iostream> 
using namespace std; 

int main() { 
int n; 
bool found = true; 
unsigned long int sum = 0; 

cin >> n; 
int i = 0; 
while (found) { 
    ++i; 
    if (n == 0) { //The code below doesn't work if n = 0, so we assign value to sum right away (in case n = 0) 
     sum = 0; 
     break; 
    } 
    int j = i; 
    while (j != 0) { //After each iteration, j's last digit gets stripped away (j /= 10), so we want to stop right when j becomes 0 
     sum += (j % 10) * (j % 10); //After each iteration, sum gets increased by *(last digit of j)^2*. (j % 10) gets the last digit of j 
     j /= 10; 
    } 
    if (sum == n) { //If we meet our problem's requirements, so that sum of j's each digit squared is equal to the given number n, loop breaks and we get our result 
     break; 
    } 
    sum = 0; //Otherwise, sum gets nullified and the loops starts over 
} 

cout << i; 

return 0; 
} 

我要找快速解決方案 問題。

Answer 1

使用動態編程。如果我們知道最優解的第一個數字，那麼其餘部分將是剩餘部分的最優解。因此，我們可以猜測第一個數字，並使用緩存計算獲得最佳目標。

def digitsum(n): 
    best = [0] 
    for i in range(1, n+1): 
     best.append(min(int(str(d) + str(best[i - d**2]).strip('0')) 
         for d in range(1, 10) 
         if i >= d**2)) 
    return best[n] 

Answer 2

（編輯）此答案不正確。貪婪的方法不適用於這個問題 - 對不起。

我會用一種語言不可知的方式給出我的解決方案，即算法。 我沒有測試過，但我相信這應該做的伎倆，而複雜性是成正比的數字輸出數量：

digitSquared(n) { 

     % compute the occurrences of each digit 
     numberOfDigits = [0 0 0 0 0 0 0 0 0] 
     for m from 9 to 1 { 

     numberOfDigits[m] = n/m*m; 
     n = n % m*m; 
      if (n==0) 
      exit loop; 
     } 

    % assemble the final output 
    output = 0 
    powerOfTen = 0 
    for m from 9 to 1 { 
     for i from 0 to numberOfDigits[m] { 
     output = output + m*10^powerOfTen 
     powerOfTen = powerOfTen + 1 
     } 
    } 

    } 

Answer 3

讓我們試着解釋大衛的解決方案。我相信他的假設是，給出最佳的解決方案，abcd...，爲n - a^2最佳的解決辦法是bcd...，因此，如果我們計算所有的解決方案，從1到n，我們可以依靠以前的解決方案比n小的數字，因爲我們嘗試不同的減法。

那麼我們如何解讀David的代碼呢？

（1）通過n放置爲數字1的方案中，在順序，在表best：

for i in range(1, n+1): 
    best.append(... 

（2）用於當前查詢，i該溶液中，是在陣列中的最小如果從i減去d^2是可行的，那麼d，1和9之間的選擇是可行的。

轉換成整數的最小...

min(int(

...的字符串，d，與n - d^2先前記錄在表中的解決方案的字符串連接在一起的（除去溶液的串聯零）：

 str(d) + str(best[i - d**2]).strip('0') 

讓我們修改的大衛的代碼的最後一行，就看的表是如何工作的一個例子：

def digitsum(n): 
    best = [0] 
    for i in range(1, n+1): 
     best.append(min(int(str(d) + str(best[i - d**2]).strip('0')) 
         for d in range(1, 10) 
         if i >= d**2)) 

    return best # original line was 'return best[n]' 

我們打電話，digitsum(10)：

=> [0, 1, 11, 111, 2, 12, 112, 1112, 22, 3, 13] 

當我們得到i = 5，我們爲d選擇是1和2這樣的選擇的排列是：

min([ int(str(1) + str(best[5 - 1])), int(str(2) + str(best[5 - 4])) ]) 
=> min([ int( '1' +  '2'  ), int( '2' +  '1'  ) ]) 

等等等等。

Answer 4

所以這實際上是一個衆所周知的變相問題。 The minimum coin change problem其中給你一筆錢，並要求用最少數量的硬幣支付。在這裏，我們有81,64,49,36，...，1美分，而不是一個，鎳，硬幣和宿舍。

顯然這是一個鼓勵動態規劃的典型例子。在動態規劃中，不同於預期自上而下的遞歸方法，現在預計您將從下到上「記憶」後面將要求的結果。因此......快得多..！

所以確定這裏是我在JS的方法。這可能與David的方法非常類似。

function getMinNumber(n){ 
 
    var sls = Array(n).fill(), 
 
     sct = [], max; 
 
    sls.map((_,i,a) => { max = Math.min(9,~~Math.sqrt(i+1)), 
 
         sct = []; 
 
         while (max) sct.push(a[i-max*max] ? a[i-max*max].concat(max--) 
 
                 : [max--]); 
 
         a[i] = sct.reduce((p,c) => p.length < c.length ? p : c); 
 
        }); 
 
    return sls[sls.length-1].reverse().join(""); 
 
} 
 
console.log(getMinNumber(500));

我們正在做的是從下到上生成查找陣列稱爲sls。這是發生記憶的地方。然後從1開始到n我們正在映射幾個選項中的最佳結果。例如，如果我們要查找10的分區，我們將從10的平方根的整數部分開始，它是3並將其保留在max變量中。所以3是其中一個數字，另一個應該是10-3 * 3 = 1.然後我們查找先前解決的1，其實際上是[1]，在sls[0]，並且連接3到sls[0]。結果是[3,1]。一旦我們完成了3然後一個一個我們開始在同一個工作，一個較小，直到它是1.所以3後，我們檢查2（結果是[2,2,1,1]），然後爲1（結果是[1,1,1,1,1,1,1,1,1,1]），並比較長度最短的結果爲3,2和1，即[3,1]並將其存儲在sls[9]（又名a[i]），這是我們查找數組中的10的位置。