Dado un número N, la tarea es contar todos los ‘a’ y ‘b’ que satisfacen la condición a^2 + b^2 = N.
Nota:- (a, b) y (b, a) deben ser considerados como dos pares diferentes y (a, a) también es válido y debe considerarse una sola vez.
Ejemplos:
Input: N = 10 Output: 2 1^2 + 3^2 = 10 3^2 + 1^2 = 10 Input: N = 8 Output: 1 2^2 + 2^2 = 8
Acercarse:
- Recorre los números del 1 a la raíz cuadrada de N.
- Resta el cuadrado del número actual de N y verifica si su diferencia es un cuadrado perfecto o no.
- Si es un cuadrado perfecto, incremente el conteo.
- Cuenta de vuelta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count pairs whose sum
// of squares is N
#include <bits/stdc++.h>
using namespace std;
// Function to count the pairs satisfying
// a ^ 2 + b ^ 2 = N
int countPairs(int N)
{
int count = 0;
// Check for each number 1 to sqrt(N)
for (int i = 1; i <= sqrt(N); i++) {
// Store square of a number
int sq = i * i;
// Subtract the square from given N
int diff = N - sq;
// Check if the difference is also
// a perfect square
int sqrtDiff = sqrt(diff);
// If yes, then increment count
if (sqrtDiff * sqrtDiff == diff)
count++;
}
return count;
}
// Driver code
int main()
{
// Loop to Count no. of pairs satisfying
// a ^ 2 + b ^ 2 = i for N = 1 to 10
for (int i = 1; i <= 10; i++)
cout << "For n = " << i << ", "
<< countPairs(i) << " pair exists\n";
return 0;
}
Java
// Java program to count pairs whose sum
// of squares is N
import java.io.*;
class GFG {
// Function to count the pairs satisfying
// a ^ 2 + b ^ 2 = N
static int countPairs(int N)
{
int count = 0;
// Check for each number 1 to sqrt(N)
for (int i = 1; i <= (int)Math.sqrt(N); i++)
{
// Store square of a number
int sq = i * i;
// Subtract the square from given N
int diff = N - sq;
// Check if the difference is also
// a perfect square
int sqrtDiff = (int)Math.sqrt(diff);
// If yes, then increment count
if (sqrtDiff * sqrtDiff == diff)
count++;
}
return count;
}
// Driver code
public static void main (String[] args)
{
// Loop to Count no. of pairs satisfying
// a ^ 2 + b ^ 2 = i for N = 1 to 10
for (int i = 1; i <= 10; i++)
System.out.println( "For n = " + i + ", "
+ countPairs(i) + " pair exists\n");
}
}
// This code is contributed by inder_verma.
Python 3
# Python 3 program to count pairs whose sum
# of squares is N
# From math import everything
from math import *
# Function to count the pairs satisfying
# a ^ 2 + b ^ 2 = N
def countPairs(N) :
count = 0
# Check for each number 1 to sqrt(N)
for i in range(1, int(sqrt(N)) + 1) :
# Store square of a number
sq = i * i
# Subtract the square from given N
diff = N - sq
# Check if the difference is also
# a perfect square
sqrtDiff = int(sqrt(diff))
# If yes, then increment count
if sqrtDiff * sqrtDiff == diff :
count += 1
return count
# Driver code
if __name__ == "__main__" :
# Loop to Count no. of pairs satisfying
# a ^ 2 + b ^ 2 = i for N = 1 to 10
for i in range(1,11) :
print("For n =",i,", ",countPairs(i),"pair exists")
# This code is contributed by ANKITRAI1
C#
// C# program to count pairs whose sum
// of squares is N
using System;
class GFG {
// Function to count the pairs satisfying
// a ^ 2 + b ^ 2 = N
static int countPairs(int N)
{
int count = 0;
// Check for each number 1 to Sqrt(N)
for (int i = 1; i <= (int)Math.Sqrt(N); i++)
{
// Store square of a number
int sq = i * i;
// Subtract the square from given N
int diff = N - sq;
// Check if the difference is also
// a perfect square
int sqrtDiff = (int)Math.Sqrt(diff);
// If yes, then increment count
if (sqrtDiff * sqrtDiff == diff)
count++;
}
return count;
}
// Driver code
public static void Main ()
{
// Loop to Count no. of pairs satisfying
// a ^ 2 + b ^ 2 = i for N = 1 to 10
for (int i = 1; i <= 10; i++)
Console.Write( "For n = " + i + ", "
+ countPairs(i) + " pair exists\n");
}
}
PHP
<?php
// PHP program to count pairs
// whose sum of squares is N
// Function to count the pairs
// satisfying a ^ 2 + b ^ 2 = N
function countPairs($N)
{
$count = 0;
$i = 0;
// Check for each number 1 to sqrt(N)
for ($i = 1; $i <= sqrt($N); $i++)
{
// Store square of a number
$sq = $i * $i;
// Subtract the square
// from given N
$diff =$N - $sq;
// Check if the difference
// is also a perfect square
$sqrtDiff = sqrt($diff);
// If yes, then increment count
if ($sqrtDiff * $sqrtDiff == $diff)
$count++;
}
return $count;
}
// Driver code
// Loop to Count no. of pairs satisfying
// a ^ 2 + b ^ 2 = i for N = 1 to 10
for ($i = 1; $i <= 10; $i++)
echo "For n = " . $i . ", " .
countPairs($i) . " pair exists\n";
// This code is contributed by Raj
?>
Javascript
<script>
// Javascript program to count pairs whose sum
// of squares is N
// Function to count the pairs satisfying
// a ^ 2 + b ^ 2 = N
function countPairs(N)
{
let count = 0;
// Check for each number 1 to sqrt(N)
for (let i = 1; i <= Math.sqrt(N); i++) {
// Store square of a number
let sq = i * i;
// Subtract the square from given N
let diff = N - sq;
// Check if the difference is also
// a perfect square
let sqrtDiff = Math.sqrt(diff);
// If yes, then increment count
if (sqrtDiff * sqrtDiff == diff)
count++;
}
return count;
}
// Driver code
// Loop to Count no. of pairs satisfying
// a ^ 2 + b ^ 2 = i for N = 1 to 10
for (let i = 1; i <= 10; i++)
document.write("For n = " + i + ", "
+ countPairs(i) + " pair exists<br>");
// This code is contributed by rishavmahato348.
</script>
Producción:
For n = 1, 1 pair exists For n = 2, 1 pair exists For n = 3, 0 pair exists For n = 4, 1 pair exists For n = 5, 2 pair exists For n = 6, 0 pair exists For n = 7, 0 pair exists For n = 8, 1 pair exists For n = 9, 1 pair exists For n = 10, 2 pair exists
Complejidad del tiempo : O(sqrt(N))
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA