algorithm - 最初の k 桁の合計と同じ最後の k 桁の合計

Question

特定の範囲内のいくつかの数字の最初の k 桁の合計が最後の k 桁の合計と等しいかどうかを調べたい。ここでは範囲が非常に大きく、k は 20 未満です。

これを行う 1 つの方法は、力ずくの方法です。誰かが他の効率的なアルゴリズムを提案できますか? 同じですか？

Answer 1

範囲の場合、最初の桁は頻繁に変更されず、最後の桁は単純な方法で変更されます。S は最初の 20 桁の合計です。秒の桁は変わりませんが、次の桁に進むと合計が 1 増えます。したがって、最後の数字を除くすべての数字が固定されていて、最後の数字が i に等しい合計が Si である場合、最後の数字は n= S - Si + i のみが有効です。次に、n が 0 から 9 の間であるかどうか、および結果の数値が間隔内にあるかどうかを確認する必要があります。これにより、ルックアップの数が 10 減少します。

次の秒の下位桁を確認できます。
最初の n が 0 より小さい場合は、秒の桁を -n だけ減らす必要があります。この 2 番目の数字を n2 と呼びます。n2 > = 0 の場合、適切な数値は (n2,0)、(n2 -1,1)、...、(0, n2) で終わります。これにより、複雑さが 100 減少します。n が 10 より大きい場合は、2 桁目を n-9 増やします。n2 を 2 桁目に呼び出します。n2<=9 の場合、適切な数値は (n2,9),(n2-1,8),...,(0,something) です。これにより、複雑さも 100 減少します。

同じことを 3 桁目、4 桁目、20 まで行うことができます。これにより、合計は 1 つだけになり、O(解の数) の複雑さになるため、最小になります。コーディングについては、最初の数字が変わる可能性があることに注意してください。最初の 20 個の数字のグループごとに 1 つの計算を行います。

Answer 2

ブルートフォースに対する別の改善：

i = 0, T = 0
while |T| < 9 * (k - i) 
  T = T + last[i] - first[i]
  i = i + 1
return T == 0 

Answer 3

同じ配列に対してそれを複数回使用する場合は、すべての要素を前の要素と合計することができます。これはO(n)、配列のサイズです。n

for(int i = 1; i < n; i++)
     arr[i] = arr[i] + arr[i-1];

これにより、配列が確率密度関数から累積分布関数(離散数の場合) に変換されます。したがって、クエリは次のようになりO(1)ます

if(arr[k-1] == (arr[n-1]-arr[n-k])) //arr[k-1] is sum of first k element
    return true;
return false;