Reputation:

Pythagorean Triplet with given sum

The following code prints the pythagorean triplet if it is equal to the input, but the problem is that it takes a long time for large numbers like 90,000 to answer. What can I do to optimize the following code? 1 ≤ n ≤ 90 000

def pythagoreanTriplet(n):

    # Considering triplets in
    # sorted order. The value
    # of first element in sorted
    # triplet can be at-most n/3.
    for i in range(1, int(n / 3) + 1):

        # The value of second element
        # must be less than equal to n/2
        for j in range(i + 1,
                       int(n / 2) + 1):

            k = n - i - j
            if (i * i + j * j == k * k):
                print(i, ", ", j, ", ",
                      k, sep="")
                return

    print("Impossible")
# Driver Code
vorodi = int(input())
pythagoreanTriplet(vorodi)

Upvotes: -3

Answers (4)

AYUSH PATEL

Reputation: 1

the given function takes array and tells whether there is a pythagoream triplets or not

//User function template for C++
class Solution{
public:
    // Function to check if the
    // Pythagorean triplet exists or not
    bool checkTriplet(int arr[], int n) {
        // code here
        
        map<int,int> m;
        int l=-1;
        for(int i=0;i<n;i++){
            m[arr[i]]++;
            l=max(l,arr[i]);
        }
        
        for(int i=1;i<=l;i++)
        {
            if(m[i]!=0)
            {
                for(int j=i+1;j<=l;j++)
                {
                    if(m[j]!=0)
                    {
                        int c=sqrt(i*i+j*j);
                        if(c*c==i*i+j*j){if(m[c]!=0) return true;};
                    }
                }
            }
        }
        return false;
        
    }
};

Upvotes: 0

Abhijit Sarkar

Reputation: 24528

DarrylG's answer is correct, and I've added the missing steps to it as well, but there's another solution that's faster than iterating from [1, n). Let me explain it, but I'll leave the code up to the reader.

We use Euclid's formula of generating a tuple.

a = m^2 - n^2, b = 2mn, c = m^2 + n^2, where m > n > 0 ---(i)
a + b + c = P ---(ii)

Combining equations (i) and (ii), we have:

2m^2 + 2mn = P ---(iii)

Since m > n > 0, 1 <= n <= m - 1. Putting n=1 in equation (iii), we have:

2m^2 + 2m - P = 0, ax^2 + bx + c = 0, a=2, b=2, c=-P
 m = (-b +- sqrt(b^2 - 4ac)) / 2a
 => (-2 +- sqrt(4 + 8P)) / 4
 => (-1 +- sqrt(1 + 2P)) / 2

Since m > 0, sqrt(b^2 - 4ac) > -b, the only solution is

 (-1 + sqrt(1 + 2P)) / 2 ---(iv)

Putting n=m-1 in equation (iii), we have:

2m^2 + 2m(m - 1) - P = 0
 => 4m^2 - 2m - P = 0, ax^2 + bx + c = 0, a=4, b=-2, c=-P
 m = (-b +- sqrt(b^2 - 4ac)) / 2a
 => (2 +- sqrt(4 + 16P)) / 8
 => (1 +- sqrt(1 + 4P)) / 4

Since m > 0, the only solution is

(1 + sqrt(1 + 4P)) / 4 ---(v)

From equation (iii), m^2 + mn = P/2; since P/2 is constant, when n is the smallest, m must be the largest, and vice versa.

Thus:

(1 + sqrt(1 + 4P)) / 4 <= m <= (-1 + sqrt(1 + 2P)) / 2 ---(vi)

Solving equation (iii) for n, we have:

 n = (P - 2m^2) / 2m ---(vii)

We iterate for m within the bounds given by the inequality (vi) and check when the corresponding n given by equation (vii) is an integer.

Despite generating all primitive triples, Euclid's formula does not produce all triples - for example, (9, 12, 15) cannot be generated using integer m and n. This can be remedied by inserting an additional parameter k to the formula. The following will generate all Pythagorean triples uniquely.

a = k(m^2 - n^2), b = 2kmn, c = k(m^2 + n^2), for k >= 1.

Thus, we iterate for integer values of P/k until P < 12, lowest possible perimeter corresponding to the triple (3, 4, 5).

Upvotes: 0

DarrylG

Reputation: 17156

Your source code does a brute force search for a solution so it's slow.

Faster Code

def solve_pythagorean_triplets(n):
  " Solves for triplets whose sum equals n "
  solutions = []
  for a in range(1, n):
    denom = 2*(n-a)
    num = 2*a**2 + n**2 - 2*n*a
    if denom > 0 and num % denom == 0:
      c = num // denom
      b = n - a - c
      if b > a:
        solutions.append((a, b, c))

  return solutions

OP code

Modified OP code so it returns all solutions rather than printing the first found to compare performance

def pythagoreanTriplet(n): 
  
    # Considering triplets in  
    # sorted order. The value  
    # of first element in sorted  
    # triplet can be at-most n/3. 
    results = []
    for i in range(1, int(n / 3) + 1):  
          
        # The value of second element  
        # must be less than equal to n/2 
        for j in range(i + 1,  
                       int(n / 2) + 1):  
  
            k = n - i - j 
            if (i * i + j * j == k * k):
                results.append((i, j, k))
      
    return results

Timing

 n     pythagoreanTriplet (OP Code)     solve_pythagorean_triplets (new)
  900   0.084 seconds                       0.039 seconds
  5000  3.130 seconds                       0.012 seconds
  90000 Timed out after several minutes     0.430 seconds

Explanation

Function solve_pythagorean_triplets is O(n) algorithm that works as follows.

Searching for:

a^2 + b^2 = c^2 (triplet)
a + b + c = n   (sum equals input)

Solve by searching over a (i.e. a fixed for an iteration). With a fixed, we have two equations and two unknowns (b, c):
```
b + c = n - a
c^2 - b^2 = a^2
```

Solution is:

denom = 2*(n-a)
num = 2*a**2 + n**2 - 2*n*a
if denom > 0 and num % denom == 0:
    c = num // denom
    b = n - a - c
    if b > a:
        (a, b, c) # is a solution

Iterate a range(1, n) to get different solutions

Edit June 2022 by @AbhijitSarkar:

For those who like to see the missing steps:

c^2 - b^2 = a^2
b + c = n - a
=> b = n - a - c

c^2 - (n - a - c)^2 = a^2
=> c^2 - (n - a - c) * (n - a - c) = a^2
=> c^2 - n(n - a - c) + a(n - a - c) + c(n - a - c) = a^2
=> c^2 - n^2 + an + nc + an - a^2 - ac + cn - ac - c^2 = a^2
=> -n^2 + 2an + 2nc - a^2 - 2ac = a^2
=> -n^2 + 2an + 2nc - 2a^2 - 2ac = 0
=> 2c(n - a) = n^2 - 2an + 2a^2
=> c = (n^2 - 2an + 2a^2) / 2(n - a)

Upvotes: 3

Bourn Again

Reputation: 1

Yo I don't know if you still need the answer or not but hopefully, this can help.

n = int(input())
ans = [(a, b, c) for a in range(1, n) for b in range(a, n) for c in range(b, n) if (a**2 + b**2 == c**2 and a + b + c == n)]
if ans:
    print(ans[0][0], ans[0][1], ans[0][2])
else:
    print("Impossible")

Upvotes: -1

Pythagorean Triplet with given sum

Answers (4)

Related Questions