We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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 105 test queries.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #39: Integer right triangles
You are viewing a single comment's thread. Return to all comments →
Here are some hints:
1. Generate all the Pythagorean triples using primitive Pythagorean triples (with perimeter <= 5*106).
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 105 test queries.