# Count of pair of integers (x , y) such that difference between square of x and y is a perfect square

Given an integer N. The task is to find the number of pairs of integers (x, y) both less than N and greater than 1, such that **x ^{2} – y **is a square number or 0.

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 3Output:2Explanation:

The only possible valid pairs are (1, 1), (2, 3). Therefore, the count of such pairs is 2.

Input:N = 2Output:1

**Naive Approach:** The simplest approach to solve the given problem is to generate all possible **pairs of integers**** (x, y)** over the range **[1, N]** and then check that if the value of **(x ^{2} – y)** is a perfect square or not. If found to be

**true**, then count this pair. After checking for all the possible, print the total count obtained.

**Time Complexity:** O(N^{2}) **Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can also be optimized by the following observation:

xis a square of a number, let’s say square of^{2}-yz.

x^{2}– y = z^{2 }

x^{2}– z^{2}= y

( x + z ) * ( x – z ) = yNow, let

x + z = pandx – z = q

p * q = y

So, the problem gets reduced to count the pairs of **p, q** instead of **x, y**.

Now, as y can only be in the range of **1** to** N**

So, **p*q** will also be in the range from 1 to N. And as **p>=q** ( because **x+z >= x-z **), **q** will be in the range from **1 to âˆšN** and p will be in the range of **1 to N/q**.

Also

p+q = 2*x, sox = (p+q)/2.

Now, asxcan have a max value ofN, therefore(p+q)/2 <= Np <= 2*N-q

So, the max value of** p = min ( 2*N – q, N/q).**

Now, after knowing the ranges of **p** & **q, **try all possible values of **p** & **q**. And after fixing, all possible pairs possible are **(l, q)** where** l **is in the range from **q** to maximum value of **p.**

So, the total number of pairs formed are **(p – q + 1)**, say **cnt**.

Now, as we know that **p=x+z** and **q=x-z, **so both **p** & **q** are either even or odd. And based on this conclusion, if **q** is even the total valid pairs are **cnt/2 (after removing all pairs with an** **even value of p)** and if it is odd then the total number of valid pairs are **(cnt/2 + 1)**.

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 number of pairs` `// (x, y) such that x^2 - y is a` `// square number` `int` `countPairs(` `int` `N)` `{` ` ` `// Stores the count of total pairs` ` ` `int` `res = 0;` ` ` `// Iterate q value 1 to sqrt(N)` ` ` `for` `(` `int` `q = 1; q * q <= N; q++) {` ` ` `// Maximum possible value of p is` ` ` `// min(2 * N - q, N / q)` ` ` `int` `maxP = min(2 * N - q, N / q);` ` ` `// P must be greater than or` ` ` `// equal to q` ` ` `if` `(maxP < q)` ` ` `continue` `;` ` ` `// Total number of pairs are` ` ` `int` `cnt = maxP - q + 1;` ` ` `// Adding all valid pairs to res` ` ` `res += (cnt / 2 + (cnt & 1));` ` ` `}` ` ` `// Return total no of pairs (x, y)` ` ` `return` `res;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 3;` ` ` `cout << countPairs(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` `// Function to find number of pairs` `// (x, y) such that x^2 - y is a` `// square number` `static` `int` `countPairs(` `int` `N)` `{` ` ` ` ` `// Stores the count of total pairs` ` ` `int` `res = ` `0` `;` ` ` `// Iterate q value 1 to Math.sqrt(N)` ` ` `for` `(` `int` `q = ` `1` `; q * q <= N; q++) {` ` ` `// Maximum possible value of p is` ` ` `// Math.min(2 * N - q, N / q)` ` ` `int` `maxP = Math.min(` `2` `* N - q, N / q);` ` ` `// P must be greater than or` ` ` `// equal to q` ` ` `if` `(maxP < q)` ` ` `continue` `;` ` ` `// Total number of pairs are` ` ` `int` `cnt = maxP - q + ` `1` `;` ` ` `// Adding all valid pairs to res` ` ` `res += (cnt / ` `2` `+ (cnt & ` `1` `));` ` ` `}` ` ` `// Return total no of pairs (x, y)` ` ` `return` `res;` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `3` `;` ` ` `System.out.print(countPairs(N));` `}` `}` `// This code is contributed by 29AjayKumar` |

## Python3

`# python program for the above approach` `import` `math` `# Function to find number of pairs` `# (x, y) such that x^2 - y is a` `# square number` `def` `countPairs(N):` ` ` `# Stores the count of total pairs` ` ` `res ` `=` `0` ` ` `# Iterate q value 1 to sqrt(N)` ` ` `for` `q ` `in` `range` `(` `1` `, ` `int` `(math.sqrt(N)) ` `+` `1` `):` ` ` `# Maximum possible value of p is` ` ` `# min(2 * N - q, N / q)` ` ` `maxP ` `=` `min` `(` `2` `*` `N ` `-` `q, N ` `/` `/` `q)` ` ` `# P must be greater than or` ` ` `# equal to q` ` ` `if` `(maxP < q):` ` ` `continue` ` ` `# Total number of pairs are` ` ` `cnt ` `=` `maxP ` `-` `q ` `+` `1` ` ` `# Adding all valid pairs to res` ` ` `res ` `+` `=` `(cnt ` `/` `/` `2` `+` `(cnt & ` `1` `))` ` ` `# Return total no of pairs (x, y)` ` ` `return` `res` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `3` ` ` `print` `(countPairs(N))` `# This code is contributed by rakeshsahni` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG` `{` ` ` ` ` `// Function to find number of pairs` ` ` `// (x, y) such that x^2 - y is a` ` ` `// square number` ` ` `static` `int` `countPairs(` `int` `N)` ` ` `{` ` ` ` ` `// Stores the count of total pairs` ` ` `int` `res = 0;` ` ` `// Iterate q value 1 to sqrt(N)` ` ` `for` `(` `int` `q = 1; q * q <= N; q++) {` ` ` `// Maximum possible value of p is` ` ` `// min(2 * N - q, N / q)` ` ` `int` `maxP = Math.Min(2 * N - q, N / q);` ` ` `// P must be greater than or` ` ` `// equal to q` ` ` `if` `(maxP < q)` ` ` `continue` `;` ` ` `// Total number of pairs are` ` ` `int` `cnt = maxP - q + 1;` ` ` `// Adding all valid pairs to res` ` ` `res += (cnt / 2 + (cnt & 1));` ` ` `}` ` ` `// Return total no of pairs (x, y)` ` ` `return` `res;` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `Main()` ` ` `{` ` ` `int` `N = 3;` ` ` `Console.WriteLine(countPairs(N));` ` ` `}` `}` `// This code is contributed by ukasp.` |

## Javascript

`<script>` ` ` `// JavaScript Program to implement` ` ` `// the above approach` ` ` `// Function to find number of pairs` ` ` `// (x, y) such that x^2 - y is a` ` ` `// square number` ` ` `function` `countPairs(N) {` ` ` `// Stores the count of total pairs` ` ` `let res = 0;` ` ` `// Iterate q value 1 to sqrt(N)` ` ` `for` `(let q = 1; q * q <= N; q++) {` ` ` `// Maximum possible value of p is` ` ` `// min(2 * N - q, N / q)` ` ` `let maxP = Math.min(2 * N - q, N / q);` ` ` `// P must be greater than or` ` ` `// equal to q` ` ` `if` `(maxP < q)` ` ` `continue` `;` ` ` `// Total number of pairs are` ` ` `let cnt = maxP - q + 1;` ` ` `// Adding all valid pairs to res` ` ` `res += Math.floor(cnt / 2 + (cnt & 1));` ` ` `}` ` ` `// Return total no of pairs (x, y)` ` ` `return` `res;` ` ` `}` ` ` `// Driver Code` ` ` `let N = 3;` ` ` `document.write(countPairs(N));` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output:**

2

**Time Complexity:** O(N^{1/2}) **Auxiliary Space:** O(1)