Given a number N, the task is to count all ‘a’ and ‘b’ that satisfy the condition a^2 + b^2 = N.
Note:- (a, b) and (b, a) are to be considered as two different pairs and (a, a) is also valid and to be considered only one time.
Examples:
Input: N = 10 Output: 2 1^2 + 3^2 = 10 3^2 + 1^2 = 10 Input: N = 8 Output: 1 2^2 + 2^2 = 8
Approach:
- Traverse numbers from 1 to square root of N.
- Subtract square of the current number from N and check if their difference is a perfect square or not.
- If it is perfect square then increment the count.
- Return count.
Below is the implementation of above approach:
C++
// C++ program to count pairs whose sum// of squares is N#include <bits/stdc++.h>using namespace std;// Function to count the pairs satisfying// a ^ 2 + b ^ 2 = Nint countPairs(int N){ int count = 0; // Check for each number 1 to sqrt(N) for (int i = 1; i <= sqrt(N); i++) { // Store square of a number int sq = i * i; // Subtract the square from given N int diff = N - sq; // Check if the difference is also // a perfect square int sqrtDiff = sqrt(diff); // If yes, then increment count if (sqrtDiff * sqrtDiff == diff) count++; } return count;}// Driver codeint main(){ // Loop to Count no. of pairs satisfying // a ^ 2 + b ^ 2 = i for N = 1 to 10 for (int i = 1; i <= 10; i++) cout << "For n = " << i << ", " << countPairs(i) << " pair exists\n"; return 0;} |
Java
// Java program to count pairs whose sum // of squares is N import java.io.*;class GFG {// Function to count the pairs satisfying // a ^ 2 + b ^ 2 = N static int countPairs(int N) { int count = 0; // Check for each number 1 to sqrt(N) for (int i = 1; i <= (int)Math.sqrt(N); i++) { // Store square of a number int sq = i * i; // Subtract the square from given N int diff = N - sq; // Check if the difference is also // a perfect square int sqrtDiff = (int)Math.sqrt(diff); // If yes, then increment count if (sqrtDiff * sqrtDiff == diff) count++; } return count; } // Driver code public static void main (String[] args) { // Loop to Count no. of pairs satisfying // a ^ 2 + b ^ 2 = i for N = 1 to 10 for (int i = 1; i <= 10; i++) System.out.println( "For n = " + i + ", " + countPairs(i) + " pair exists\n"); }}// This code is contributed by inder_verma. |
Python 3
# Python 3 program to count pairs whose sum # of squares is N # From math import everythingfrom math import *# Function to count the pairs satisfying # a ^ 2 + b ^ 2 = N def countPairs(N) : count = 0 # Check for each number 1 to sqrt(N) for i in range(1, int(sqrt(N)) + 1) : # Store square of a number sq = i * i # Subtract the square from given N diff = N - sq # Check if the difference is also # a perfect square sqrtDiff = int(sqrt(diff)) # If yes, then increment count if sqrtDiff * sqrtDiff == diff : count += 1 return count# Driver code if __name__ == "__main__" : # Loop to Count no. of pairs satisfying # a ^ 2 + b ^ 2 = i for N = 1 to 10 for i in range(1,11) : print("For n =",i,", ",countPairs(i),"pair exists") # This code is contributed by ANKITRAI1 |
C#
// C# program to count pairs whose sum // of squares is N using System; class GFG { // Function to count the pairs satisfying // a ^ 2 + b ^ 2 = N static int countPairs(int N) { int count = 0; // Check for each number 1 to Sqrt(N) for (int i = 1; i <= (int)Math.Sqrt(N); i++) { // Store square of a number int sq = i * i; // Subtract the square from given N int diff = N - sq; // Check if the difference is also // a perfect square int sqrtDiff = (int)Math.Sqrt(diff); // If yes, then increment count if (sqrtDiff * sqrtDiff == diff) count++; } return count; } // Driver code public static void Main () { // Loop to Count no. of pairs satisfying // a ^ 2 + b ^ 2 = i for N = 1 to 10 for (int i = 1; i <= 10; i++) Console.Write( "For n = " + i + ", " + countPairs(i) + " pair exists\n"); }} |
PHP
<?php// PHP program to count pairs // whose sum of squares is N // Function to count the pairs // satisfying a ^ 2 + b ^ 2 = N function countPairs($N) { $count = 0; $i = 0; // Check for each number 1 to sqrt(N) for ($i = 1; $i <= sqrt($N); $i++) { // Store square of a number $sq = $i * $i; // Subtract the square // from given N $diff =$N - $sq; // Check if the difference // is also a perfect square $sqrtDiff = sqrt($diff); // If yes, then increment count if ($sqrtDiff * $sqrtDiff == $diff) $count++; } return $count; } // Driver code // Loop to Count no. of pairs satisfying // a ^ 2 + b ^ 2 = i for N = 1 to 10 for ($i = 1; $i <= 10; $i++) echo "For n = " . $i . ", " . countPairs($i) . " pair exists\n"; // This code is contributed by Raj?> |
Javascript
<script>// Javascript program to count pairs whose sum// of squares is N// Function to count the pairs satisfying// a ^ 2 + b ^ 2 = Nfunction countPairs(N){ let count = 0; // Check for each number 1 to sqrt(N) for (let i = 1; i <= Math.sqrt(N); i++) { // Store square of a number let sq = i * i; // Subtract the square from given N let diff = N - sq; // Check if the difference is also // a perfect square let sqrtDiff = Math.sqrt(diff); // If yes, then increment count if (sqrtDiff * sqrtDiff == diff) count++; } return count;}// Driver code // Loop to Count no. of pairs satisfying // a ^ 2 + b ^ 2 = i for N = 1 to 10 for (let i = 1; i <= 10; i++) document.write("For n = " + i + ", " + countPairs(i) + " pair exists<br>");// This code is contributed by rishavmahato348.</script> |
Output:
For n = 1, 1 pair exists For n = 2, 1 pair exists For n = 3, 0 pair exists For n = 4, 1 pair exists For n = 5, 2 pair exists For n = 6, 0 pair exists For n = 7, 0 pair exists For n = 8, 1 pair exists For n = 9, 1 pair exists For n = 10, 2 pair exists
Time Complexity : O(sqrt(N))
Auxiliary Space: O(1)
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!
