# Project Euler #39: Integer right triangles

# Project Euler #39: Integer right triangles

trojan38f + 2 comments This is the algorithm I used:

Generate all Pythagorean triplets(pt) by Euclid's method. a = m*m-n*n; b = 2*m*n; c = m*m+n*n; for all m>n>0 and m and n are integers. For primitive pt gcd(m,n)==1 and one of m or n should be even.

thus the sum of a+b+c = p will be 2*m*(m+n); Since perimeter is only 5*10^6 then iterate m till 1200.

To generate all non primitive pt just multiply by k(>0) every value of a, b, c. Thus perimeter of all non primitive pt will be k*2*m*(m+n).

now the algorithm:

for(m = 2 to 1200) // including 1200 for(n = 1 to m) // excluding m if (m+n)%2!=0 and gcd(m,n)==1 perimeter = 2*m*(m+n) for(k=1 to infinity) if k*p > 5000000 then break; else freq[k*p]++;

Here freq[p] has count of all values of pt whose perimeter is p.

now make another array which stores the largest number less than n whose number of pt's is max.

simply the condition will be:

if(freq[i]>freq[b[i-1]]) b[i] = i; else b[i] = b[i-1];

now for every input n output b[n];

:)

Rakesh882 + 1 comment can code it in 2 min but how did u get the idea of m and n?How are you sure that You get the exact count?What is the logic behind it?

trojan38f + 1 comment It is Euclid's method to generate all primitive pythagorean triplets.

See this visualization in geometry: https://en.wikipedia.org/wiki/Pythagorean_triple#Geometry_of_Euclid.27s_formula

SOKS33 + 0 comments Thanks for all the info. The last loop is killing me in python though. Timeout when using 5000000 as my limit

khoangcachxalam1 + 1 comment thanks for your very very good idea ! if you do not tutorial , maybe I will not be do this problem ! one again , thanks you very much :)

trojan38f + 0 comments You're welcome

andragon + 2 comments First of all hi everybody. My question might sound stupid, but if i have successfully solved a contest problem is there any way to see the solutions of other competitors for that problem? I ask because for the domain problems this i know how to do, but here i don't see any option to view a competitors solution. I would like to see this for this problem because even though i solved the problem, i did so very, very ugly and i am looking for a nicer and more enlightening solution. Thanks in advance :D

shashank21jHackerRank AdminChallenge Author + 0 comments We'll soon add such a feature.

ankur1000 + 0 comments yes exactly like codechef has, hackerrank too must give such option for us to learn coding by looking at best solutions

IMLearner + 1 comment [12, 60, 120, 240, 420, 720, 840, 1680, 2520, 4620] this is the array i got. I am getting WA error for test case 4 and above. Can u tell me where is the problem?

below is my python3 solution for reference

import os import sys from math import sqrt from bisect import bisect_left from collections import defaultdict def binary_search(a, x, lo=0, hi=None): # can't use a to specify default for hi hi = hi if hi is not None else len(a) # hi defaults to len(a) pos = bisect_left(a, x, lo, hi) # find insertion position return (pos if pos != hi and a[pos] == x else -1) # don't walk off the end def binarySearch(data, val): highIndex = len(data)-1 lowIndex = 0 while highIndex > lowIndex: index = int((highIndex + lowIndex) / 2) sub = data[index] if data[lowIndex] == val: return [lowIndex, lowIndex] elif sub == val: return [index, index] elif data[highIndex] == val: return [highIndex, highIndex] elif sub > val: if highIndex == index: return sorted([highIndex, lowIndex]) highIndex = index else: if lowIndex == index: return sorted([highIndex, lowIndex]) lowIndex = index return sorted([highIndex, lowIndex]) s = [(i+1)*(i+1) for i in range(2300)] d = defaultdict(lambda:0) for i in range(len(s)): for j in range(i+1,len(s)): k = binary_search(s,s[i]+s[j])+1 if k!=0: d[(i+1+j+1+k)]+=1 temp = list(sorted(list(d.keys()))) ans = list() maxValue = 0 for i in temp: if d[i]>maxValue: ans+=[i] #print(d[i],i) maxValue = d[i] #print(ans) ans += [5000001] for i in range(int(input())): temp = int(input()) l,h = binarySearch(ans,temp) print(ans[l])

dingma129 + 2 comments the array should contain more element, for example 5040

IMLearner + 0 comments Yes, Thanks for help. I figured that out and realised that we should focus on constraints all the time. #sillyMistakes become so confusing sometimes. We think too hard for little problems.

bhavikgevariya + 0 comments & after that 9240

padeff + 0 comments hum, pypy version timed out, whiel the python2 version worked. Wonder the cause. I time < to 0,8 sec on the 4 first test in pypy, and time out on the 2 last.

anand_10 + 0 comments Python is getting Time Limit Exceeded Error while C++14 is doing it in 100ms

So astonishing

chaa1 + 0 comments A good question!! learnt something new :D

harshitagarwal37 + 1 comment my method 1)varing a from 1 to n 2)varying b from 1 to a 3)c=p-a-b 4)checking if a^2+b^2=c^2 5)correspondingly selecting the value of p

but this method is quite lengthy,timeout for case#2 and above.

Suggest a efficient method.

msram + 0 comments Here are some hints:

1.**Generate all the Pythagorean triples using primitive Pythagorean triples**(with perimeter <= 5*10^{6}).

2.**Build 2 hashmaps**: one that maps each perimeter to number of solutions with that perimeter; and another that maps each perimeter p1 to perimeter p2 <= p1, where p2 is the perimeter with maximum number of solutions before p1.

3. Precompute these hashmaps before reading any input and for each input N, do an**O(log N) search**.

I implemented it in Python and it takes ~7s for the precomputation and ~1.5s to answer 10^{5}test queries.

bayleef + 2 comments What should we output if we have two maximum values below n?

shashank21jHackerRank AdminChallenge Author + 0 comments Smallest one

bayleef + 0 comments Maybe it should be mentioned in statement then. My second submission outputs the largest one but I think it's correct otherwise.

No more comments

Sort 8 Discussions, By:

Please Login in order to post a comment