Given a positive integer N, the task is to find the count of pairs of integers (x, y) whose difference of squares is equal to N, i.e.,
Examples:
Input: N = 20
Output: 4
Explanation:
The 4 possible pairs are (10, 2), (-10, 2), (-10, -2) and (10, -2).Input: N = 80
Output: 12
Explanation:
The 12 possible pairs are:
1. (40, 2), (-40, 2), (-40, -2) and (40, -2).
2. (20, 4), (-20, 4), (-20, -4) and (20, -4).
3. (10, 8), (-10, 8), (-10, -8) and (10, -8).
Approach:
The given equation can also be written as:
=>
=>
Now for an integral solution of the given equation:
(x+y)(x-y)
is always an integer
=> (x+y)(x-y)
are divisors of N
Let (x + y) = p1 and (x + y) = p2
be the two equations where p1 & p2 are the divisors of N
such that p1 * p2 = N.
Solving for the above two equations we have:
=>
and
From the above calculations, for x and y to be integral, then the sum of divisors must be even. Since there are 4 possible values for two values of x and y as (+x, +y), (+x, -y), (-x, +y) and (-x, -y).
Therefore the total number of possible solutions is given by 4*(count pairs of divisors with even sum).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the integral// solutions of the given equationvoid findSolutions(int N){ // Initialise count to 0 int count = 0; // Iterate till sqrt(N) for (int i = 1; i <= sqrt(N); i++) { if (N % i == 0) { // If divisor's pair sum is even if ((i + N / i) % 2 == 0) { count++; } } } // Print the total possible solutions cout << 4 * count << endl;}// Driver Codeint main(){ // Given number N int N = 80; // Function Call findSolutions(N); return 0;} |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the integral // solutions of the given equation static void findSolutions(int N) { // Initialise count to 0 int count = 0; // Iterate till sqrt(N) for(int i = 1; i <= Math.sqrt(N); i++) { if (N % i == 0) { // If divisor's pair sum is even if ((i + N / i) % 2 == 0) { count++; } } } // Print the total possible solutions System.out.print(4 * count);} // Driver codepublic static void main(String[] args) { // Given number N int N = 80; // Function Call findSolutions(N); } } // This code is contributed by Shubham Prakash. |
Python3
# Python3 program for the above approachimport math;# Function to find the integral# solutions of the given equationdef findSolutions(N): # Initialise count to 0 count = 0; # Iterate till sqrt(N) for i in range(1, int(math.sqrt(N)) + 1): if (N % i == 0): # If divisor's pair sum is even if ((i + N // i) % 2 == 0): count += 1; # Print the total possible solutions print(4 * count);# Driver Code# Given number NN = 80;# Function CallfindSolutions(N);# This code is contributed by Code_Mech |
C#
// C# program for the above approach using System;class GFG{ // Function to find the integral // solutions of the given equation static void findSolutions(int N) { // Initialise count to 0 int count = 0; // Iterate till sqrt(N) for(int i = 1; i <= Math.Sqrt(N); i++) { if (N % i == 0) { // If divisor's pair sum is even if ((i + N / i) % 2 == 0) { count++; } } } // Print the total possible solutions Console.Write(4 * count);} // Driver codepublic static void Main(String[] args) { // Given number N int N = 80; // Function Call findSolutions(N); } } // This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program for the above approach// Function to find the integral// solutions of the given equationfunction findSolutions(N){ // Initialise count to 0 let count = 0; // Iterate till sqrt(N) for(let i = 1; i <= Math.sqrt(N); i++) { if (N % i == 0) { // If divisor's pair sum is even if ((i + parseInt(N / i)) % 2 == 0) { count++; } } } // Print the total possible solutions document.write(4 * count + "<br>");}// Driver Code// Given number Nlet N = 80;// Function CallfindSolutions(N);// This code is contributed by souravmahato348</script> |
12
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
