PythagorasLegs | Topcoder Archive

Problem Statement

Pythagoras showed that for right triangles (triangles where one of the angles is 90 degrees) the lengths of the sides are related by the formula A² + B² = C² where C is the length of the hypotenuse (the side opposite the right angle and always the longest of the three sides) and the sides with lengths A and B are called the "legs" of the triangle.

The cases where the lengths are integer values are the most interesting. If C is a given positive integer, then valid pairs of integer lengths (satisfying the equation for the given C) for sides A and B may not exist, or one or more pairs of valid positive integer values may exist.

Given the hypotenuse length, C, return the shortest strictly positive integer leg length which, along with some other strictly positive integer length for the other leg, forms a valid right triangle with all sides having positive integer lengths. If no such triangle is possible, return 0.

For example if C=13 then A=5,B=12 forms a valid right triangle so you would return 5, the smallest leg.

Definition

Class:: PythagorasLegs
Method:: shortest
Parameters:: int
Returns:: int
Method signature:: int shortest(int C)
(be sure your method is public)

Notes

Intermediate values are likely to overflow 32 bit integers.
If you are using C++ for this problem, be aware that the GNU C++ datatype for 64 bit integers is long long.

Constraints

C will be between 1 and 1000000 inclusive.

Examples

```
13
```
```
Returns: 5
```
The example above, the (5,12,13) triangle.
```
17
```
```
Returns: 8
```
```
1000000
```
```
Returns: 75840
```
```
999998
```
```
Returns: 0
```
```
5150
```
```
Returns: 1442
```
```
2520
```
```
Returns: 1512
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.