# Project Euler #75: Singular integer right triangles

# Project Euler #75: Singular integer right triangles

ErikTillema + 0 comments Solved this problem in F# using Euclid's formula to generate primitive Pythagorean triplets, for each increasing the triplet count of the appropriate lenghts (ie, multiples of the sum of the triplet values). With some simple DP, one then has all answers precalculated. Note that this last part is useful in this particular problem, since the number of tests can be high (10^5).

froz3nshade + 0 comments Lazy solution to dumb test cases: precalculate all the counts up to N=5e6 then return the corresponding value for each test case. You really should put more effort (or at least

*some*effort) into reasonable/decent/interesting requirements.

xerx593 + 1 comment Please give any hints regarding timeouts@tc4-6! A local profiling run on my submission (java.lang, T=10000, N in 4990000..5000000, no input scanning) executes in 2.767 seconds...Tc0-3 pass either (~20 ms).

xerx593 + 0 comments `Scanner -> BufferedReader`

,`List<Integer> -> int[]`

, aggergated generation (of the triplets) and evaluation (of results) did it by the end of the day: Congratz 2me, thx anyway 2you

Shreeram214 + 0 comments any one can send code for this answer

kitchent + 0 comments Was stuck with the mindset to calculate the primitive triplets of a given perimeter (loop based on the perimeter) one after another, and it was too slow.

Then I swiched to looping on odd and even

`m`

and its corresponding`n`

, and even with occasional`gcd()`

does not make it unacceptably slow. The rest is just implementation of precalculation and dynamic programming. Takes more than 2s in Python, though.

Dalimil + 0 comments There is a typo in the challenge title.

VKbhardwaj + 1 comment For 50 the answer should be 0. Because according to your answer that is 6 which is only possible when you add all the right triangles of length <50. But according to your question the lenght of wire must be equal to the sum of all the sides of triangle for eg-12-(3,4,5)->3+4+5=12 but if you are giving 50 as your input and giving 6 as an output which means that you are incresing your count values for 12,24,30,36,40,48 which gives you answer 6. while doing that you are contradiciting 1 condition that is sum of edges should be equal to the given length. please reply me soon with your suggestion.

merv28 + 1 comment Read carefully the problem and what should be the output, you are getting it:

"Because according to your answer that is 6 which is only possible when you add all the right triangles of length <50"

Mohan_Krishnan + 1 comment Well,the question is clear, but the example about "120" is absurd.By following the question 120 has 22 possibilities of forming a integer sided triangle.

merv28 + 1 comment I can see in your profile that you are Indian, and I suppose that English is not your native language. Many times the problem statement is an extra challenge for us that do not speak English natively, and is something that we must learn to overcome. A single word can change the things a lot, and the answer of the problem.

Mohan_Krishnan + 0 comments Yup...I completely agree with you on that...and btw it's "for us who do not" not "for us 'that' do not"...:P..no offence...:)

clintonrocks13 + 3 comments 50cm answer should be 0

allamaprabhu7 + 0 comments [deleted]bunnydev + 0 comments Yes it should be 0

rahulpadhy + 1 comment Admin, can you please take a look at my code and tell where I am going wrong ? I am getting WA for the last 3 test cases.. Here's my submission ID: https://www.hackerrank.com/contests/projecteuler/challenges/euler075/submissions/code/7222502

tommytosto + 1 comment maybe you stopped your m too soon (in my case I solved stopping m a little later...)

rahulpadhy + 1 comment Can you please be a bit clearer ?

tommytosto + 0 comments the first step of my algorithm is to generate all the primitive triples and their multiples with perimeter less or equal 5*10^6 using Euclid's formula, and in first instance I assumed that m<=1200 was sufficient to generate al the triples (I've approximated n=m, so max perimeter was near 4*1200^2) but this way I was loosing some triangles generated by higher m...

bharata1803 + 0 comments Please help me, I got wrong answer for every test case, but I don't know what is wrong with my solution. Below is my algorithm to check whether there is any 1 solution or not:

`def CalculateSol(L): max = L/4 sol = [] for a in xrange(1,max+1): b = (L*L-2*L*a)/float(2*(L-a)) if math.floor(b)==b: # b is integer solution b = int(b) if a*a+b*b==(L-a-b)*(L-a-b): # a and b satisfy pythagoras theorem sol.append([a,b,L-a-b]) if len(sol)>1: # if solution is already more than 1 return -1 if len(sol)==1: # Solution exactly 1 return L else: return -1 def Main(N): count = 0 for L in xrange(12,N+1): if CalculateSol(L)>-1: print L count+=1 print count def input(): T = int(raw_input("")) for i in xrange(0,T): N = int(raw_input("")) Main(N)`

I manually check this function and as far as I know this return correct answer. Which case do you think this algorithm fail to calculate? I know this is slow, but I wil think about it after this gives corect result.

No more comments

Sort 10 Discussions, By:

Please Login in order to post a comment