體面數字|幫助減少時間複雜性

HackerRank Problem Statement 體面數字|幫助減少時間複雜性

我必須找到最大的「正確的數字」有'N'個數字。體面編號具有以下屬性：

=> 3, 5, or both as its digits. No other digit is allowed. 
=> Number of times 3 appears is divisible by 5. 
=> Number of times 5 appears is divisible by 3.

我的代碼完美無缺！但恐怕還遠遠高效：

輸入：

4 #number of test cases, i.e., the following 4 inputs 
1 
3 
5 
11

輸出：

-1 
555 
33333 
55555533333

我的解決方案的版本：

T = int(input()) #number of test cases 

def computePair(N): 
    multiplesOf3 = [i for i in range(N+1) if i%3 == 0] 
    if multiplesOf3 != [0]: #reversing a [0] results in a 'NoneType' 
     multiplesOf3.reverse() 
    multiplesOf5 = [i for i in range(N+1) if i%5 == 0] 

    for i in multiplesOf3: 
     for j in multiplesOf5: 
      if (i+j) == N: 
       return (i, j) 
    return -1 

for testCase in range(T): 
    N = int(input()) #test case 
    result = computePair(N) 
    if result == -1: 
     print(result) #If no such combination exists return '-1' 
    else: 
     print('5' * (result[0]) + '3' * (result[1]))

我想我的代碼有O（n^2）的時間複雜度;因爲2'for'循環。我希望這個按照O（n） - 線性的順序更高效。

這是一個非常普遍的問題：另外，您是否有時間複雜性最佳實踐的任何資源？我吮吸它。

來源

2015-07-20 Ben Sooraj M

如果您複製在代碼審查烏爾問題，PLZ刪除這個問題。國際海事組織，這個問題純粹問到一個更好的算法，這是完美的主題。 –

爲了解決這個問題，我們需要做一些意見：

the largest "decent number" having 'N' digits是包含數量最多的數字5的這將有形式5555 ... 3333 ...數
由於Number of times 5 appears is divisible by 3，所以我們有三種情況：
- 如果N除以3，所以沒有數字3。
- 如果N % 3 = 1，所以我們需要a times數字3添加到結果，並a % 3 == 1 3，使數字5 (N - a)整除的總數，所以a % 3 == 1和a % 5 == 0 - >a = 10。（請注意，a必須在所有有效值中最小）。最終的結果將有5 (N - 10)位和3
- 同樣10數字，如果N % 3 = 2，所以我們需要a times數字3添加到結果，a % 3 == 2和a % 5 == 0 - >a = 5;

有了這些觀察，就可以解決爲O這個問題（1）每個N.

來源

2015-07-20 08:53:57

很顯然，當'N <9'時你可以對特殊情況進行硬編碼。 – Kittsil

體面數字|幫助減少時間複雜性

回答

相關問題