Dadas dos arrays H y S. La array H[] contiene la longitud de la hipotenusa y la array S[] contiene el área de un triángulo rectángulo. La tarea es encontrar todos los pares posibles de (H, S) tales que podamos construir un triángulo rectángulo con hipotenusa H y área S.
Ejemplos :
Input : H[] = {1, 6, 4} ; S[] = {23, 3, 42, 14}
Output : 2
Possible pairs are {6, 3} {4, 3}
Input : H[] = {1, 6, 4, 3} ; S[] = {23, 3, 42, 5}
Output : 3
Possible pairs are {6, 3} {6, 5} {4, 3}
Diga, 
= Base del Triángulo Rectángulo 
= Altura del Triángulo Rectángulo
Por lo tanto,
area S = (a*b)/2 or, 4*S*S=a*a*b*b
También,
a2 + b2 = H2
Por lo tanto,
4*S2 = a2(H2-a2)
Resolviendo esta ecuación cuadrática en a 2 y poniendo discriminante>=0 (condición para que exista a). Obtendremos,
H2 >= 4*S For a right-angled triangle to exist with hypotenuse H and area S.
Enfoque ingenuo : El enfoque ingenuo consiste en encontrar todos los pares posibles de (H,S) y comprobar si cumplen la condición, H 2 >= 4*S . Cuente el número de pares que satisface esta condición e imprima el conteo.
A continuación se muestra la implementación del enfoque ingenuo:
C++
#include <iostream>
using namespace std;
// Function to check the condition
bool check(int H, int S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
int findPairs(int H[], int n, int S[], int m)
{
int count = 0;
// Checking all possible pairs
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (check(H[i], S[j]))
count++;
}
}
return count;
}
// Driver code
int main()
{
int H[] = { 1, 6, 4 };
int n = sizeof(H)/sizeof(H[0]);
int S[] = { 23, 3, 42, 14 };
int m = sizeof(S)/sizeof(S[0]);
cout<<findPairs(H, n, S, m);
return 0;
}
Java
class GFG
{
// Function to check the condition
static boolean check(int H, int S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
static int findPairs(int H[], int n,
int S[], int m)
{
int count = 0;
// Checkinag all possible pairs
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (check(H[i], S[j]))
count++;
}
}
return count;
}
// Driver code
public static void main(String args[])
{
int H[] = { 1, 6, 4 };
int n = H.length;
int S[] = { 23, 3, 42, 14 };
int m = S.length;
System.out.println(findPairs(H, n, S, m));
}
}
// This code is contributed
// by ankita_saini
Python3
# Python 3 implementation # of above approach # Function to check the condition def check(H, S) : # Condition for triangle to exist return H * H >= 4 * S # Function to find all pairs def findPairs(H, n, S, m): count = 0 # Checking all possible pairs for i in range(n) : for j in range(m) : if check(H[i], S[j]) : count += 1 return count # Driver Code if __name__ == "__main__" : H = [ 1, 6, 4] n = len(H) S = [ 23, 3, 42, 14] m = len(S) # function calling print(findPairs(H, n, S,m)) # This code is contributed by ANKITRAI1
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to check the condition
static bool check(int H, int S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
static int findPairs(int[] H, int n,
int[] S, int m)
{
int count = 0;
// Checkinag all possible pairs
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (check(H[i], S[j]))
count++;
}
}
return count;
}
// Driver code
public static void Main()
{
int[] H = { 1, 6, 4 };
int n = H.Length;
int[] S = { 23, 3, 42, 14 };
int m = S.Length;
Console.Write(findPairs(H, n, S, m));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP implementation of above approach
// Function to check the condition
function check($H, $S)
{
// Condition for triangle to exist
return $H * $H >= 4 * $S;
}
// Function to find all pairs
function findPairs($H, $n, $S, $m)
{
$count = 0;
// Checking all possible pairs
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $m; $j++)
{
if (check($H[$i], $S[$j]))
$count++;
}
}
return $count;
}
// Driver code
$H = array( 1, 6, 4 );
$n = count($H);
$S = array( 23, 3, 42, 14 );
$m = count($S);
echo findPairs($H, $n, $S, $m);
// This code is contributed by mits
?>
Javascript
<script>
// Function to check the condition
function check(H , S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
function findPairs(H , n , S , m)
{
var count = 0;
// Checkinag all possible pairs
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (check(H[i], S[j]))
count++;
}
}
return count;
}
// Driver code
var H = [ 1, 6, 4 ];
var n = H.length;
var S = [ 23, 3, 42, 14 ];
var m = S.length;
document.write(findPairs(H, n, S, m));
// This code is contributed by Rajput-Ji
</script>
Producción:
2
Complejidad temporal: O(n*m) donde n y m son los tamaños de la array H y S respectivamente.
Espacio Auxiliar: O(1)
Enfoque eficiente : un enfoque eficiente consiste en ordenar las arrays disponibles en orden creciente. Luego, para cada longitud posible de la hipotenusa, aplique la búsqueda binaria para encontrar el área máxima que satisfaga la condición necesaria.
Digamos que, después de la búsqueda binaria, el área máxima posible está disponible en el índice 4 de la array S[]. Entonces podemos formar 4 pares posibles de este tipo, ya que todas las áreas menores que la del índice 4 también cumplirán la condición.
A continuación se muestra la implementación del enfoque eficiente:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check the condition
bool check(int H, int S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
int findPairs(int H[], int n, int S[], int m)
{
int count = 0;
// Sort both the arrays
sort(H, H + n);
sort(S, S + m);
// To keep track of last possible Area
int index = -1;
for (int i = 0; i < n; i++) {
// Apply Binary Search for
// each Hypotenuse Length
int start = 0;
int end = m - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (check(H[i], S[mid])) {
index = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
// Check if we get any
// possible Area or Not
if (index != -1) {
// All area less than area[index]
// satisfy property
count += index + 1;
}
}
return count;
}
// Driver code
int main()
{
int H[] = { 1, 6, 4 };
int n = sizeof(H)/sizeof(H[0]);
int S[] = { 23, 3, 42, 14 };
int m = sizeof(S)/sizeof(S[0]);
cout<<findPairs(H, n, S, m);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.util.Arrays;
import java.io.*;
class GFG {
// Function to check the condition
static boolean check(int H, int S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
static int findPairs(int H[], int n, int S[], int m)
{
int count = 0;
// Sort both the arrays
Arrays.sort(H);
Arrays.sort(S);
// To keep track of last possible Area
int index = -1;
for (int i = 0; i < n; i++) {
// Apply Binary Search for
// each Hypotenuse Length
int start = 0;
int end = m - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (check(H[i], S[mid])) {
index = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
// Check if we get any
// possible Area or Not
if (index != -1) {
// All area less than area[index]
// satisfy property
count += index + 1;
}
}
return count;
}
// Driver code
public static void main (String[] args) {
int H[] = { 1, 6, 4 };
int n = H.length;
int S[] = { 23, 3, 42, 14 };
int m = S.length;
System.out.println(findPairs(H, n, S, m));
}
// This code is contributed
// by ajit...
}
Python3
# Function to check the condition def check(H, S): # Condition for triangle to exist return H * H >= 4 * S; # Function to find all pairs def findPairs(H, n, S, m): count = 0; # Sort both the arrays H.sort(); S.sort(); # To keep track of last possible Area index = -1; for i in range(n): # Apply Binary Search for # each Hypotenuse Length start = 0; end = m - 1; while (start <= end): mid = int(start + (end - start) / 2); if (check(H[i], S[mid])): index = mid; start = mid + 1; else: end = mid - 1; # Check if we get any possible # Area or Not if (index != -1): # All area less than area[index] # satisfy property count += index + 1; return count; # Driver code H = [ 1, 6, 4 ]; n = len(H); S= [ 23, 3, 42, 14 ]; m = len(S); print(findPairs(H, n, S, m)); # This code is contributed by mits
C#
/*package whatever //do not write package name here */
using System;
public class GFG{
// Function to check the condition
static bool check(int H, int S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
static int findPairs(int []H, int n, int []S, int m)
{
int count = 0;
// Sort both the arrays
Array.Sort(H);
Array.Sort(S);
// To keep track of last possible Area
int index = -1;
for (int i = 0; i < n; i++) {
// Apply Binary Search for
// each Hypotenuse Length
int start = 0;
int end = m - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (check(H[i], S[mid])) {
index = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
// Check if we get any
// possible Area or Not
if (index != -1) {
// All area less than area[index]
// satisfy property
count += index + 1;
}
}
return count;
}
// Driver code
static public void Main (){
int []H = { 1, 6, 4 };
int n = H.Length;
int []S = { 23, 3, 42, 14 };
int m = S.Length;
Console.WriteLine(findPairs(H, n, S, m));
}
// This code is contributed
// by akt_mit...
}
PHP
<?php
// Function to check the condition
function check($H, $S)
{
// Condition for triangle to exist
return $H * $H >= 4 * $S;
}
// Function to find all pairs
function findPairs($H, $n, $S, $m)
{
$count = 0;
// Sort both the arrays
sort($H);
sort($S);
// To keep track of last possible Area
$index = -1;
for ($i = 0; $i < $n; $i++)
{
// Apply Binary Search for
// each Hypotenuse Length
$start = 0;
$end = $m - 1;
while ($start <= $end)
{
$mid = $start + (int)($end - $start) / 2;
if (check($H[$i], $S[$mid]))
{
$index = $mid;
$start = $mid + 1;
}
else
{
$end = $mid - 1;
}
}
// Check if we get any possible
// Area or Not
if ($index != -1)
{
// All area less than area[index]
// satisfy property
$count += $index + 1;
}
}
return $count;
}
// Driver code
$H = array( 1, 6, 4 );
$n = sizeof($H);
$S = array(23, 3, 42, 14 );
$m = sizeof($S);
echo findPairs($H, $n, $S, $m);
// This code is contributed by Sach_Code
?>
Javascript
<script>
// Function to check the condition
function check(H, S)
{
// Condition for triangle to exist
return H * H >= 4 * S;
}
// Function to find all pairs
function findPairs(H, n, S, m)
{
let count = 0;
// Sort both the arrays
H.sort(function(a, b){return a - b});
S.sort(function(a, b){return a - b});
// To keep track of last possible Area
let index = -1;
for (let i = 0; i < n; i++) {
// Apply Binary Search for
// each Hypotenuse Length
let start = 0;
let end = m - 1;
while (start <= end) {
let mid = start +
parseInt((end - start) / 2, 10);
if (check(H[i], S[mid])) {
index = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
// Check if we get any
// possible Area or Not
if (index != -1) {
// All area less than area[index]
// satisfy property
count += index + 1;
}
}
return count;
}
let H = [ 1, 6, 4 ];
let n = H.length;
let S = [ 23, 3, 42, 14 ];
let m = S.length;
document.write(findPairs(H, n, S, m));
</script>
Producción:
2
Complejidad de tiempo: O(n*log(n)+m*log(m)+n*log(m)) donde n y m son los tamaños de la array H y S respectivamente. Aquí n*log(n) y m*log(m) son para ordenar la array y n*log(m) es para recorrer y aplicar la búsqueda binaria cada vez.
Espacio Auxiliar: O(1)