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 x2 – y is a square number or 0.
Example:
Input: N = 3
Output: 2
Explanation:
The only possible valid pairs are (1, 1), (2, 3). Therefore, the count of such pairs is 2.Input: N = 2
Output: 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 (x2 – 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.
C++
// C++ code for above approach#include <bits/stdc++.h>using namespace std;// Check if number is perfect square// or not.bool checkperfectsquare(int n){ // If ceil and floor are equal // the number is a perfect // square if (ceil((double)sqrt(n)) == floor((double)sqrt(n))) { return true; } else { return false; }}// Function to Count of pair of integers (x , y) // such that difference between square of x // and y is a perfect squareint countPairs(int N){ // Variable to store count int count=0; for (int x = 1; x <= N; x++) { for (int y = 1; y <= N; y++) { int diff = x * x - y; if (checkperfectsquare(diff)) { count++; } } } // Total count of pairs that satisfy the conditions cout << count << endl;}// Driver codeint main() { int N =3; countPairs(N); return 0;}// This code is contributed by Utkarsh Kumar |
Java
// Java code for above approachimport java.util.*;public class Main { // Check if number is perfect square // or not. public static boolean checkperfectsquare(int n) { // If ceil and floor are equal // the number is a perfect // square if (Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n))) { return true; } else { return false; } } // Function to Count of pair of integers (x , y) // such that difference between square of x // and y is a perfect square public static int countPairs(int N) { // Variable to store count int count = 0; for (int x = 1; x <= N; x++) { for (int y = 1; y <= N; y++) { int diff = x * x - y; if (checkperfectsquare(diff)) { count++; } } } // Total count of pairs that satisfy the conditions System.out.println(count); return count; } // Driver code public static void main(String[] args) { int N = 3; countPairs(N); }} |
Python3
import math# Check if number is perfect square# or not.def checkperfectsquare(n): # If n is negative, it is not a perfect square if n < 0: return False # If ceil and floor are equal # the number is a perfect # square if math.ceil(math.sqrt(n)) == math.floor(math.sqrt(n)): return True else: return False# Function to Count of pair of integers (x , y) # such that difference between square of x # and y is a perfect squaredef countPairs(N): # Variable to store count count=0 for x in range(1,N+1): for y in range(1,N+1): diff = x*x - y if checkperfectsquare(diff): count += 1 # Total count of pairs that satisfy the conditions print(count)# Driver codeif __name__ == '__main__': N = 3 countPairs(N) |
C#
using System;using System.Collections.Generic;class Gfg{ // Check if number is perfect square // or not. static bool checkperfectsquare(int n) { // If ceil and floor are equal // the number is a perfect // square if (Math.Ceiling((double)Math.Sqrt(n)) == Math.Floor((double)Math.Sqrt(n))) { return true; } else { return false; } } // Function to Count of pair of integers (x , y) // such that difference between square of x // and y is a perfect square static void countPairs(int N) { // Variable to store count int count=0; for (int x = 1; x <= N; x++) { for (int y = 1; y <= N; y++) { int diff = x * x - y; if (checkperfectsquare(diff)) { count++; } } } // Total count of pairs that satisfy the conditions Console.WriteLine(count); } // Driver code public static void Main(String[] args) { int N =3; countPairs(N); }} |
Javascript
// Check if number is perfect square// or not.function checkperfectsquare(n) { // If ceil and floor are equal // the number is a perfect // square if (Math.ceil(Math.sqrt(n)) == Math.floor(Math.sqrt(n))) { return true; } else { return false; }}// Function to Count of pair of integers (x , y) // such that difference between square of x // and y is a perfect squarefunction countPairs(N){ // Variable to store count let count = 0; for (let x = 1; x <= N; x++) { for (let y = 1; y <= N; y++) { let diff = x * x - y; if (checkperfectsquare(diff)) { count++; } } } // Total count of pairs that satisfy the conditions console.log(count);}// Driver codeconst N = 3;countPairs(N); |
Output
2
Time Complexity: O(N2 *LogN)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by the following observation:
x2-y is a square of a number, let’s say square of z.
x2 – y = z2
x2 – z2 = y
( x + z ) * ( x – z ) = yNow, let x + z = p and x – 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, so x = (p+q)/2.
Now, as x can have a max value of N, therefore
(p+q)/2 <= N
p <= 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 numberint 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 Codeint main(){ int N = 3; cout << countPairs(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find number of pairs// (x, y) such that x^2 - y is a// square numberstatic 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 Codepublic 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 approachimport math# Function to find number of pairs# (x, y) such that x^2 - y is a# square numberdef 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 Codeif __name__ == "__main__": N = 3 print(countPairs(N))# This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing 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(N1/2)
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!
