Algorithm to determine whether a given number N ca

Question

Suppose you are given hypotenuse of a right angled triangle,then how can you determine whether there are two integral smaller sides possible with the given hypotenuse.

For example, you are given hypotenuse as 5.Then you have to determine whether you have smaller integral sides for the given right triangle.The answer will be yes because we can have smaller sides as 3 and 4,hence getting a 3-4-5 right triangle.

Similarly,for hypotenuse as 7 we can have no such right triangle.

In other words,we have to find whether a given number N can serve as hypotenuse for a right triangle with all 3 sides as integers.

I went through entire article on Pythagorean triples but still no success.I am confused what conditions to check.Please help.

Answer 1

What about this one?

• the "smaller" sides should be smaller, obviously, than the hypotenuse of the triangle.
• we are going to need two more sides.

-> 2 for loops continues to the hypotenuse. something like this one:

public static boolean isAnIntegerTriangle(int hypotenuse) {
    for (int i = 0; i < hypotenuse; i++) {
        for (int j = 0; j < hypotenuse; j++) {
            boolean b = ((hypotenuse * hypotenuse) == (i * i + j * j));
            if (b)
                return true;
        }
    }
    return false;
}

Test:

public static void main(String[] args) {
    System.out.println(isAnIntegerTriangle(5));
    System.out.println(isAnIntegerTriangle(10));
    System.out.println(isAnIntegerTriangle(7));
}

Output:

true
true
false

Answer 2

int hypo = 5, i;
double other = 0;
for (i=1;i<hypo;i++)
{
    other = Math.sqrt(hypo*hypo - i*i);
    if (other == (int)other)
        break;
}

if (i<hypo)
   System.out.println("Yes - (" + (int)other + ", " + i +")" );
else
   System.out.println("No");

O(N)

Answer 3

You have for a primitive pythagorean triple:

(p^2 - q^2)^2 + (2 * p * q))^2 = (p^2 + q^2)^2 = N^2

Suppose p >= q. Then we have

N >= 2 * q^2 or q <= sqrt(N / 2)

Suppose N = 13. Then we need q <= sqrt(13 / 2) = 2.54

q = 2 => p^2 = 13 - 4 = 9, which is a square.

Hence you can have a small loop of numbers 'i' from 1..sqrt(N/2) and check if N - (i^2) is a square.

This will be O(sqrt(N)) for a member of a primitive pythagorean tuple.

Sample code in C/C++:

#include <stdio.h>
#include <math.h>

void CheckTuple(int n)
{
    int k = sqrt(n/2.0);

    for (int i = 1; i <= k; i++) {
        int tmp = sqrt((double)(n - i * i));
        if ((tmp * tmp) == (n - i * i)) {
            printf("%d^2 + %d^2 = %d^2\n", (tmp*tmp - i*i), 2 * tmp * i, n);
            return;
        }
    }
    printf("%d is not part of a tuple\n", n);
    return;
}


int main(int argc, char *argv[])
{

    CheckTuple(5);
    CheckTuple(6);
    CheckTuple(13);
    CheckTuple(10);
    CheckTuple(25);

    return 0;
}

Output:

3^2 + 4^2 = 5^2
6 is not part of a tuple
5^2 + 12^2 = 13^2
8^2 + 6^2 = 10^2
7^2 + 24^2 = 25^2

Answer 4

This question has been one of my most searched topics on the net. But solution is simple. Coming to the answer let n can be hypotenuse of a right angled triangle. n^2 = a^2 + b^2. (n,a and b are integers). Then obviously for any integer k, k*n can be hypotenuse. Any prime number of the form (4*l+1) can be hypotenuse (l is an integer). So, split a number into its prime factors. If at least one of the prime factor is in the form 4*l+1 , then obviously the number can be hypotenuse. Eg : 5 can be expressed as 4*1+1 and 5^2 = 3^2 + 4^2. Similarly, 78 = 2*3*13 and 13 can be expressed as 4*3+1. and 13^2 = 5^2 + 12^2 =>78^2 = 30^2 + 72^2

Answer 5

EDIT: NO need to perform the following step, because it will always return false.

//For each element in the array check whether twice its value equals N^2. If no match occurs then continue to the following.

.

Have two counters I1 and I2 -> Initialize I1 = 1 and I2 = N-1.
1. Check the sum I1^2 + I2^2;  
2. If the sum is > N^2, decrement the right counter (I2).  
3. If it is < N^2, increment the left counter (I1).

Keep doing the above 3 statements until one of the following happens.    
-> If the sum matches N^2, then a right angled triangle can be formed.
-> If I2 <= I1, then it is not possible to form a triangle.

Complexity : O(N)

EDIT: As Dukeling points out, there is no need to store an array. You can directly square I1 and I2 as you go.