HackerRankプロジェクトオイラー＃1

Question

このコードで何が問題になっていますか？ケース2 & 3をHackerRankに渡していません。

T=long(input()) 
while T>0: 
    N=long(input()) 
    sum=0 
    for i in range (1,N): 
     if i%3==0 or i%5==0: 
      sum+=i 
    print (sum) 
    T-=1 

私はプログラミングでは新しく、私が間違ったことを理解できません。

https://www.hackerrank.com/contests/projecteuler/challenges/euler001

Answer 1

コードの問題がいくつかあります。最初にlongを使用しているので、Python 2で実行していると思います。Python 2のrangeはlistを生成し、問題の説明で最大Nが10^9であるためメモリ不足になります。その代わりにxrangeに切り替えて、xrange objectを返すことで問題を解決できます。

上記の変更を行うと、2番目の問題はスピードになります。最大Nは10^5なので、あまりにも時間がかかりすぎる10^14の数値を繰り返し処理する必要があります。修正するためには、使用するアルゴリズムを変更する必要があります。数式n * (n + 1) * mul/2を使用して、範囲0...nのmulの倍数の合計を計算することができます。次に、あなただけの3と5の倍数の和を追加することにより、ケースを解決し、15の倍数を引く：正常な動作です

def sum_multiples(num, mul): 
    n = num/mul 
    return n * (n + 1) * mul/2 

for _ in xrange(int(raw_input())): 
    num = int(raw_input()) - 1 
    print sum_multiples(num, 3) + sum_multiples(num, 5) - sum_multiples(num, 15)