Dado un entero N , la tarea es encontrar dos enteros no negativos A y B , tales que A 2 – B 2 = N . Si no existen tales enteros, imprima -1 .
Ejemplos:
Entrada: N = 7
Salida: 4 3
Explicación:
Los dos números enteros 4 y 3 se pueden representar como 4 2 – 3 2 = 7 .
Entrada: N = 6
Salida: -1
Explicación:
No existe ningún par de (A, B) que satisfaga la condición requerida.
Acercarse:
- A 2 – B 2 se puede representar como (A – B) * (A + B) .
A 2 – B 2 = (A – B) * (A + B)
- Así, para que A 2 – B 2 sea igual a N , tanto (A + B) como (A – B) deben ser divisores de N .
- Considerando que A + B y A – B son iguales a C y D respectivamente, entonces C y D deben ser divisores de N tales que C ≤ D y C y D deben ser de la misma paridad.
- Por lo tanto, para resolver este problema, solo necesitamos encontrar cualquier par C y D que satisfaga la condición anterior. Si no existe tal C & D , entonces la impresión -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find two numbers
// with difference of their
// squares equal to N
#include <bits/stdc++.h>
using namespace std;
// Function to check and print
// the required two positive integers
void solve(int n)
{
// Iterate till sqrt(n) to find
// factors of N
for (int x = 1; x <= sqrt(n); x++) {
// Check if x is one
// of the factors of N
if (n % x == 0) {
// Store the factor
int small = x;
// Compute the other factor
int big = n / x;
// Check if the two factors
// are of the same parity
if (small % 2 == big % 2) {
// Compute a and b
int a = (small + big) / 2;
int b = (big - small) / 2;
cout << a << " "
<< b << endl;
return;
}
}
}
// If no pair exists
cout << -1 << endl;
}
// Driver Code
int main()
{
int n = 7;
solve(n);
return 0;
}
Java
// Java Program to find two numbers
// with difference of their
// squares equal to N
import java.util.*;
class GFG{
// Function to check and print
// the required two positive integers
static void solve(int n)
{
// Iterate till sqrt(n) to find
// factors of N
for (int x = 1; x <= Math.sqrt(n); x++)
{
// Check if x is one
// of the factors of N
if (n % x == 0)
{
// Store the factor
int small = x;
// Compute the other factor
int big = n / x;
// Check if the two factors
// are of the same parity
if (small % 2 == big % 2)
{
// Compute a and b
int a = (small + big) / 2;
int b = (big - small) / 2;
System.out.print(a + " " + b);
return;
}
}
}
// If no pair exists
System.out.print(-1);
}
// Driver Code
public static void main(String args[])
{
int n = 7;
solve(n);
}
}
// This code is contributed by Code_Mech
Python3
# Python3 Program to find two numbers # with difference of their # squares equal to N from math import sqrt # Function to check and print # the required two positive integers def solve(n) : # Iterate till sqrt(n) to find # factors of N for x in range(1, int(sqrt(n)) + 1) : # Check if x is one # of the factors of N if (n % x == 0) : # Store the factor small = x; # Compute the other factor big = n // x; # Check if the two factors # are of the same parity if (small % 2 == big % 2) : # Compute a and b a = (small + big) // 2; b = (big - small) // 2; print(a, b) ; return; # If no pair exists print(-1); # Driver Code if __name__ == "__main__" : n = 7; solve(n); # This code is contributed by AnkitRai01
C#
// C# Program to find two numbers
// with difference of their
// squares equal to N
using System;
class GFG{
// Function to check and print
// the required two positive integers
static void solve(int n)
{
// Iterate till sqrt(n) to find
// factors of N
for (int x = 1; x <= Math.Sqrt(n); x++)
{
// Check if x is one
// of the factors of N
if (n % x == 0)
{
// Store the factor
int small = x;
// Compute the other factor
int big = n / x;
// Check if the two factors
// are of the same parity
if (small % 2 == big % 2)
{
// Compute a and b
int a = (small + big) / 2;
int b = (big - small) / 2;
Console.WriteLine(a + " " + b);
return;
}
}
}
// If no pair exists
Console.WriteLine(-1);
}
// Driver Code
public static void Main()
{
int n = 7;
solve(n);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// javascript Program to find two numbers
// with difference of their
// squares equal to N
// Function to check and print
// the required two positive integers
function solve(n) {
// Iterate till sqrt(n) to find
// factors of N
for (var x = 1; x <= Math.sqrt(n); x++) {
// Check if x is one
// of the factors of N
if (n % x == 0) {
// Store the factor
var small = x;
// Compute the other factor
var big = n / x;
// Check if the two factors
// are of the same parity
if (small % 2 == big % 2) {
// Compute a and b
var a = (small + big) / 2;
var b = (big - small) / 2;
document.write(a + " " + b);
return;
}
}
}
// If no pair exists
document.write(-1);
}
// Driver Code
var n = 7;
solve(n);
// This code contributed by aashish1995
</script>
Producción:
4 3
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA