Given an integer C, the task is to find all possible pairs (A, B) in range [1, C) such that:
- A2 + B2 = C2
- A < B
Examples:
Input: C = 5
Output:(3, 4)
Explanation:
(3)2 + (4)2 = 9 + 16 = 25 = 52Input: C = 25
Output:(15, 20), (7, 24)
Explanation: Both the pairs satisfy the necessary conditions.
Approach:
- Check all possible values of A and B in the range [1, C).
- Store all pair that satisfies the given conditions.
Below is the implementation of the above approach:
C++
// C++ program to compute// all the possible// pairs that forms a// pythagorean triple// with a given value#include <bits/stdc++.h>using namespace std;// Function to generate all// possible pairsvector<pair<int, int> > Pairs(int C){ // Vector to store all the // possible pairs vector<pair<int, int> > ans; // Checking all the possible // pair in the range of [1, c) for (int i = 1; i < C; i++) { for (int j = i + 1; j < C; j++) { // If the pair satisfies // the condition push it // in the vector if ((i * i) + (j * j) == (C * C)) { ans.push_back(make_pair(i, j)); } } } return ans;}// Driver Programint main(){ int C = 13; vector<pair<int, int> > ans = Pairs(C); // If no valid pair exist if (ans.size() == 0) { cout << "No valid pair exist" << endl; return 0; } // Print all valid pairs for (auto i = ans.begin(); i != ans.end(); i++) { cout << "(" << i->first << ", " << i->second << ")" << endl; } return 0;} |
Java
// Java program to compute all // the possible pairs that forms// a pythagorean triple with a // given valueimport java.util.*;class GFG{static class pair{ int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to generate all// possible pairsstatic Vector<pair> Pairs(int C){ // Vector to store all the // possible pairs Vector<pair> ans = new Vector<pair>(); // Checking all the possible // pair in the range of [1, c) for(int i = 1; i < C; i++) { for(int j = i + 1; j < C; j++) { // If the pair satisfies // the condition push it // in the vector if ((i * i) + (j * j) == (C * C)) { ans.add(new pair(i, j)); } } } return ans;}// Driver codepublic static void main(String[] args){ int C = 13; Vector<pair> ans = Pairs(C); // If no valid pair exist if (ans.size() == 0) { System.out.print("No valid pair " + "exist" + "\n"); return; } // Print all valid pairs for(pair i:ans) { System.out.print("(" + i.first + ", " + i.second + ")" + "\n"); }}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to compute all # the possible pairs that forms a # pythagorean triple with a given value # Function to generate all # possible pairs def Pairs(C): # Vector to store all the # possible pairs ans = [] # Checking all the possible # pair in the range of [1, c) for i in range(C): for j in range(i + 1, C): # If the pair satisfies # the condition push it # in the vector if ((i * i) + (j * j) == (C * C)): ans.append([i, j]) return ans; # Driver codeif __name__=="__main__": C = 13; ans = Pairs(C); # If no valid pair exist if (len(ans) == 0): print("No valid pair exist") exit() # Print all valid pairs for i in range(len(ans)): print("(" + str(ans[i][0]) + ", " + str(ans[i][1]) + ")")# This code is contributed by rutvik_56 |
C#
// C# program to compute all // the possible pairs that forms// a pythagorean triple with a // given valueusing System;using System.Collections.Generic;class GFG{class pair{ public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to generate all// possible pairsstatic List<pair> Pairs(int C){ // List to store all the // possible pairs List<pair> ans = new List<pair>(); // Checking all the possible // pair in the range of [1, c) for(int i = 1; i < C; i++) { for(int j = i + 1; j < C; j++) { // If the pair satisfies // the condition push it // in the vector if ((i * i) + (j * j) == (C * C)) { ans.Add(new pair(i, j)); } } } return ans;}// Driver codepublic static void Main(String[] args){ int C = 13; List<pair> ans = Pairs(C); // If no valid pair exist if (ans.Count == 0) { Console.Write("No valid pair " + "exist" + "\n"); return; } // Print all valid pairs foreach(pair i in ans) { Console.Write("(" + i.first + ", " + i.second + ")" + "\n"); }}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to compute// all the possible// pairs that forms a// pythagorean triple// with a given value// Function to generate all// possible pairsfunction Pairs(C){ // Vector to store all the // possible pairs var ans = []; // Checking all the possible // pair in the range of [1, c) for (var i = 1; i < C; i++) { for (var j = i + 1; j < C; j++) { // If the pair satisfies // the condition push it // in the vector if ((i * i) + (j * j) == (C * C)) { ans.push([i, j]); } } } return ans;}// Driver Programvar C = 13;var ans = Pairs(C); // If no valid pair existif (ans.length == 0) { document.write( "No valid pair exist<br>");}// Print all valid pairsans.forEach(x => { document.write( "(" + x[0] + ", " + x[1] + ")" + "<br>");});// This code is contributed by noob2000.</script> |
Output:
(5, 12)
Time Complexity: O(C2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
