Dado un número entero N. La tarea es encontrar el número de pares de números enteros (x, y) menores que N y mayores que 1, tal que x 2 – y es un número cuadrado o 0.
Ejemplo:
Entrada: N = 3
Salida: 2
Explicación:
Los únicos pares válidos posibles son (1, 1), (2, 3). Por lo tanto, la cuenta de tales pares es 2.Entrada: N = 2
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares posibles de números enteros (x, y) en el rango [1, N] y luego verificar si el valor de (x 2 – y) es un cuadrado perfecto O no. Si se encuentra que es cierto , entonces cuente este par. Después de comprobar todos los posibles, imprima el recuento total obtenido.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante la siguiente observación:
x 2 -y es el cuadrado de un número, digamos el cuadrado de z .
x 2 – y = z 2
x 2 – z 2 = y
( x + z ) * ( x – z ) = yAhora, sea x + z = p y x – z = q
p * q = y
Entonces, el problema se reduce a contar los pares de p, q en lugar de x, y .
Ahora, como y solo puede estar en el rango de 1 a N
Entonces, p*q también estará en el rango de 1 a N. Y como p>=q (porque x+z >= xz ), q estará en el rango de 1 a √N yp estará en el rango de 1 a N/q .
También p+q = 2*x , entonces x = (p+q)/2.
Ahora, como x puede tener un valor máximo de N , por lo tanto
(p+q)/2 <= N
p <= 2*Nq
Entonces, el valor máximo de p = min ( 2*N – q, N/q).
Ahora, después de conocer los rangos de p & q, pruebe todos los valores posibles de p & q . Y después de fijar, todos los posibles pares posibles son (l, q) donde l está en el rango de q al valor máximo de p.
Entonces, el número total de pares formados es (p – q + 1) , digamos cnt .
Ahora, como sabemos que p=x+z y q=xz, tanto p como q son pares o impares. Y en base a esta conclusión, si q es par, el total de pares válidos es cnt/2 (después de eliminar todos los pares con un valor par de p) y si es impar, entonces el número total de pares válidos es (cnt/2 + 1) .
A continuación se muestra la implementación del enfoque anterior:
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>
2
Complejidad de Tiempo: O(N 1/2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rakeshsahni y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA