時間/空間の複雑さの低減。プログラミングコンテスト

Question

スキルテストシステムの次のプログラミング問題を発見しました。

正の整数Nが与えられます。数列[0,1、...、N]を考える。これらの数値の小数点表現のゼロの総数はいくらですか？

Nは非常に大きくなる可能性があります。したがって、Nの10進表現を含む長さLの空でない文字列Sの形式で与えられます。Sには先行ゼロは含まれません。

関数を書く：いくつかの正の整数Nの10進表現である文字列Sを、所与、

int number_of_zeros(char *S); 


int number_of_zeros(const string &S); 

、[数値の小数点表現においてゼロの総数を返す0、1 ...、N]。結果が1,410,000,016を超える場合、関数は、結果の除算から1,410,000,017を剰余として返す必要があります。

* L is an integer within the range [1..10,000]; 
    * string S consists only of digits (0-9); 
    * string S contains no leading zeros. 

複雑：

* expected worst-case time complexity is O(L); 
    * expected worst-case space complexity is O(L) (not counting the storage required for input arguments). 

S = "100" 機能12を返すべきであり、S = "219" は42

と仮定するを返すべきであるためするための例えば

、

私はそれを解決しようとしましたが、関数を書きましたが、実行時間の複雑さは私の解決策ではO（L）よりも洗練されています 誰でも解決できますか？擬似コードまたは説明）？

大成功です！

Answer 1

この問題は、再帰の強みの良い例です。単純な基本ケースを考えてみましょう：1から1までの数字は、正確にゼロが0です。

数字が1からN（xとする）の場合、1からN * 10までの数値を9 * x + log10（N * 10）として計算できます。議論は簡単です：1、...、2、... 3の数字に等しい数のゼロで9つのブロックが必要です。数字N * 10は10000 ...と書かれています。

この再帰は10のすべての累乗に対して有効です。任意のNに対する再帰は、その数を構成する10の累乗にその数を分割するとそれほど計算が難しくありません。

Answer 2

上限が10000しかないため、これは技術的に時間空間の複雑さを軽減するコンテストで、送信コード内のすべての可能な回答を事前に計算するだけです。これは非常にメモリが非効率的であることに気づくかもしれませんが、ルックアップ値が「0」から9個以上離れている状況は決してありません。大量のメモリを節約するために辞書を使用できます。

zeros.py（L上に線形時間であるが、実際のコードを生成）：http://paste.pocoo.org/show/504589/

ランタイム〜償却O（1：

def zeros(n): 
     l = str(n) 
     return l.count("0") 

total = 0 
d = {} 
for i in xrange(10001): 
     delta = zeros(i) 
     if (delta>0): 
       total += delta 
       d[i] = total 

print len(d) 
print 
print "d = " + str(d) 
print "N = int(raw_input())" 
print "while (N not in d):" 
print "\t N-=1" 
print "print d[N]" 

この（32キロバイト）は（31MSに）ファイルを生成し）

スペース〜L = [0..10000]のゼロの密度は2621〜26.21％です。私はゼロの分布が大きく増加するとは考えていませんが、その密度はO（L）によって明確に限定されています。