Pythagorean Triplet with given sum using single loop
A Pythagorean Triplet is a set of natural numbers such that a < b < c, for which
[Tex]a^2 + b^2 = c^2[/Tex]
Given a number N, find a Pythagorean Triplet with sum given as N or return -1.
Examples:
Input: 12
Output: 3 4 5
Explanation:
32 + 42 = 52
Input: 82
Output: -1
Approach: The idea is to find the value of b and c in terms of a and iterate a from 1 to N. To find the value of b and c in terms of a we have to do following:
We have two equations,
[Tex]a^2 + b^2 = c^2 [/Tex]
[Tex]a + b + c = N[/Tex]
We will find the value of c in term of a and b Then put this value in equation 1 to solve for b.
From equation 2,
[Tex]c = N – b – a[/Tex]
Now, put this value in equation 1.
[Tex]a^2 + b^2 = (N – b – a)^2[/Tex]
After solving the above equation we will get,
[Tex]b = (N * N – 2 * N * a) / (2 * N – 2 * a) [/Tex]
[Tex]c = N – b – a[/Tex]
Now, iterate a from 1 to N and calculate respectively the value of b and c Then, check if
[Tex]a^2 + b^2 = c^2[/Tex]
// C++ program to find the Pythagorean
// Triplet with given sum
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// Pythagorean triplet in O(n)
void PythagoreanTriplet(int n)
{
int flag = 0;
// Iterate a from 1 to N-1.
for (int a = 1; a < n; a++)
{
// Calculate value of b
int b = (n * n - 2 * n * a)
/ (2 * n - 2 * a);
// The value of c = n - a - b
int c = n - a - b;
if (a * a + b * b == c * c
&& b > 0 && c > 0)
{
cout << a << " " << b << " " << c;
flag = 1;
break;
}
}
if (flag == 0) {
cout << "-1";
}
return;
}
// Driver Code
int main()
{
int N = 12;
// Function call
PythagoreanTriplet(N);
return 0;
}
// Java program to find the Pythagorean
// Triplet with given sum
class GFG {
// Function to calculate the Pythagorean triplet in O(n)
static void pythagoreanTriplet(int n) {
boolean found = false;
// Iterate a from 1 to N-1.
for (int a = 1; a < n; a++) {
// Calculate value of b
int b = (n * n - 2 * n * a) / (2 * n - 2 * a);
// Ensure b is a positive integer
if ((2 * n * a) % (2 * n - 2 * a) != 0) {
continue;
}
// The value of c = n - a - b
int c = n - a - b;
// Check if a, b, and c form a Pythagorean triplet
if (a * a + b * b == c * c && b > 0 && c > 0) {
System.out.print(a + " " + b + " " + c);
System.out.println();
found = true;
break;
}
}
if (!found) {
System.out.print("-1");
}
}
// Simplified method to find a specific type of Pythagorean triplet
public static int[] findPythagoreanTriplet(int n) {
if (n < 12 || n % 12 != 0) {
return new int[]{-1};
}
int factor = n / 12;
return new int[]{3 * factor, 4 * factor, 5 * factor};
}
// Driver Code
public static void main(String[] args) {
int N = 60;
// Function call
pythagoreanTriplet(N);
int[] triplet = findPythagoreanTriplet(N);
if (triplet[0] != -1) {
System.out.println( triplet[0] + " " + triplet[1] + " " + triplet[2]);
} else {
System.out.println("\nNo triplet found");
}
}
}
// This code contributed by saiyad ali
# Python3 program to find the Pythagorean
# Triplet with a given sum
# Function to calculate the
# Pythagorean triplet in O(n)
def PythagoreanTriplet(n):
flag = 0
# Iterate a from 1 to N-1.
for a in range(1, n, 1):
# Calculate value of b
b = (n * n - 2 * n * a) // (2 * n - 2 * a)
# The value of c = n - a - b
c = n - a - b
if (a * a + b * b == c * c
and b > 0 and c > 0):
print(a, b, c)
flag = 1
break
if(flag == 0):
print("-1")
return
# Driver code
if __name__ == '__main__':
N = 12
# Function call
PythagoreanTriplet(N)
# This code is contributed by Bhupendra_Singh
// C# program to find the Pythagorean
// Triplet with given sum
using System;
class GFG {
// Function to calculate the
// Pythagorean triplet in O(n)
static void PythagoreanTriplet(int n)
{
int flag = 0;
// Iterate a from 1 to N-1.
for (int a = 1; a < n; a++)
{
// Calculate value of b
int b = (n * n - 2 * n * a)
/ (2 * n - 2 * a);
// The value of c = n - a - b
int c = n - a - b;
if (a * a + b * b == c * c
&& b > 0 && c > 0)
{
Console.Write(a + " " + b + " " + c);
flag = 1;
break;
}
}
if (flag == 0) {
Console.Write("-1");
}
return;
}
// Driver code
public static void Main(String[] args)
{
int N = 12;
// Function call
PythagoreanTriplet(N);
}
}
// This code is contributed by shivanisinghss2110
<script>
// Javascript program to find the Pythagorean
// Triplet with given sum
// Function to calculate the
// Pythagorean triplet in O(n)
function PythagoreanTriplet(n)
{
let flag = 0;
// Iterate a from 1 to N-1.
for (let a = 1; a < n; a++)
{
// Calculate value of b
let b = (n * n - 2 * n * a)
/ (2 * n - 2 * a);
// The value of c = n - a - b
let c = n - a - b;
if (a * a + b * b == c * c
&& b > 0 && c > 0)
{
document.write(a + " " + b + " " + c);
flag = 1;
break;
}
}
if (flag == 0) {
document.write("-1");
}
return;
}
let N = 12;
// Function call
PythagoreanTriplet(N);
// This code is contributed by divyeshrabadiya
</script>
Output
3 4 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us