Project Euler Problem 1 Statement
Solution
HackerRank version
HackerRank Project Euler 1 increases the upper bound from 1,000 to 1 billion and runs 10,000 test cases. The iterative approach simply won’t work fast enough, but the presented closed–form will.
Python Source Code
import itertools,math
n=5000000
c=[0]*(n+1)
for t,s in itertools.combinations_with_replacement(range(1,math.isqrt(n),2),2):
if math.gcd(s,t)==1:
x=s*(s+t);c[x::x]=[v+1 for v in c[x::x]]
m=a=0;r=[]
for i,v in enumerate(c):
if v>m:m,a=v,i
r.append(a)
for _ in range(int(input())):print(r[int(input())])