Pythagorean Triples
InterviewTime limit1sMemory limit128 MB
Given up to 50 distinct positive integers, list all Pythagorean triples x<y<z present in the set, sorted lexicographically, or report that none exist.
- Level
Medium4 of 10
- Topics
- Hash map, Math, Sorting, Brute force
- Solved
- No attempts yet
Problem
The Avengers have reached one of Loki's dens, but a locked keypad blocks the way. Thor is convinced the key is a Pythagorean triple made from three numbers on a sequence written on a nearby wall. Help them find every such triple.
A set of three distinct integers with is called a Pythagorean triple when . For example, is a Pythagorean triple, while is not.
Given a sequence of distinct positive integers , find every Pythagorean triple whose three members all appear in the sequence.
Input
The first line contains the number of test cases ().
Each of the next lines describes one test case. The line begins with an integer (), the length of the sequence, followed by the distinct positive integers of the sequence in arbitrary order. No number exceeds .
Output
Print the answer for each test case on its own line, in the same order as the input.
If the sequence contains at least one Pythagorean triple, print the keyword, then two spaces, then every triple. Write each triple as {x y z} with and a single space between the numbers, and separate consecutive triples with a single space. List the triples in increasing order, first by , then by , then by . The line reads exactly:
Found Pythogorean triples: {x y z} {x y z} ...
If the sequence contains no Pythagorean triple, print exactly:
No Pythogorean triples found in the sequence.
The output keyword is spelled Pythogorean, exactly as shown.