Dado un número K que es el máximo número posible de diagonales en cualquier polígono, la tarea es encontrar el número de lados de ese polígono.
Ejemplos:
Entrada: 2
Salida: 4
Explicación: Un cuadrilátero tiene 2 diagonales como máximo.Entrada: 6
Salida : -1
Explicación: Ningún polígono tiene como máximo 6 diagonales.
Enfoque: Este problema se puede resolver con base en la siguiente observación matemática:
Intuición:
para un polígono convexo de n lados , desde cada vértice, podemos dibujar (n – 3) diagonales.
Siguiendo este camino para n-vértices , habrá n*(n – 3) diagonales pero cada diagonal se calcula dos veces.
Entonces el número total de diagonales se convierte en n*(n – 3)/2Por lo tanto:
n*(n – 3) / 2 = K
n*(n – 3) – 2 *K = 0
n 2 – 3*n -2*K = 0
Cuando esto se compara con la representación general de la ecuación cuadrática ( ax 2 + bx + c)
a = 1, b = -3, c = -2 *K
para esta ecuación.Resuelve la ecuación para obtener el valor de n que es:
n = (-b ± √(b 2 – 4ac) )/ 2a
Siga los pasos mencionados a continuación para implementar la idea:
- Use la fórmula derivada arriba para encontrar el valor de n :
- El discriminante d = b 2 – 4ac
- Si d > 0: las raíces serán distintas y una de las raíces positivas será la respuesta
- Si d == 0: las raíces serán iguales y esa será la respuesta
- Si d < 0: las raíces serán imaginarias y la respuesta no existe
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the roots of quadratic equation
int findRoots(int K)
{
int a = 1;
int b = -3;
int c = -2 * K;
// Finding discriminant
int d = b * b - 4 * a * c;
double sqrt_val = sqrt(abs(d));
// Root are distinct
if (d > 0) {
// roots of equation
double x1 = (-b + sqrt_val) / (2 * a);
double x2 = (-b - sqrt_val) / (2 * a);
if ((int)x1 == x1 && x1 > 0)
return (int(x1));
else if ((int)x2 == x2 && x2 > 0)
return (int(x2));
else
return -1;
}
// Roots are equal
else if (d == 0) {
// roots of equation
double x1 = (-b / (2 * a));
if ((int)x1 == x1 && x1 > 0)
return (int(x1));
else
return -1;
}
// Root are imaginary
else
return -1;
}
// Driver code
int main()
{
// K is number of diagonals
int K = 9;
// Function call
cout << findRoots(K);
return 0;
}
// This code is contributed by Rohit Pradhan
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the roots of quadratic equation
static double findRoots(int K){
int a = 1;
int b = -3;
int c = -2 * K;
// Finding discriminant
int d = b * b - 4 * a * c;
double sqrt_val = Math.sqrt(Math.abs(d));
// Root are distinct
if (d > 0) {
// roots of equation
double x1 = (-b + sqrt_val) / (2 * a);
double x2 = (-b - sqrt_val) / (2 * a);
if ((int)x1 == x1 && x1 > 0)
return x1;
else if ((int)x2 == x2 && x2 > 0)
return x2;
else
return -1;
}
// Roots are equal
else if (d == 0)
{
// roots of equation
double x1 = (-b / (2 * a));
if ((int)x1 == x1 && x1 > 0)
return x1;
else
return -1;
}
// Root are imaginary
else
return -1;
}
// Driver code
public static void main (String[] args)
{
// K is number of diagonals
int K = 9;
// Function call
System.out.println((int) findRoots(K));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python3 program for the above approach import math # Function to find the roots of quadratic equation def findRoots(K): a = 1 b = -3 c = -2 * K # Finding discriminant d = b * b - 4 * a * c sqrt_val = math.sqrt(abs(d)) # Root are distinct if d > 0: # roots of equation x1 = (-b + sqrt_val)/(2 * a) x2 = (-b - sqrt_val)/(2 * a) if int(x1) == x1 and x1 > 0: return (int(x1)) elif int(x2) == x2 and x2 > 0: return (int(x2)) else: return -1 # Roots are equal elif d == 0: # roots of equation x1 = (-b / (2 * a)) if int(x1) == x1 and x1 > 0: return (int(x1)) else: return -1 # Root are imaginary else: return -1 # Driver code if __name__ == '__main__': # K is number of diagonals K = 9 # Function call print(findRoots(K))
C#
// C# code for the above discussed approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the roots of quadratic equation
static double findRoots(int K)
{
int a = 1;
int b = -3;
int c = -2 * K;
// Finding discriminant
int d = b * b - 4 * a * c;
double sqrt_val = Math.Sqrt(Math.Abs(d));
// Root are distinct
if (d > 0) {
// roots of equation
double x1 = (-b + sqrt_val) / (2 * a);
double x2 = (-b - sqrt_val) / (2 * a);
if ((int)x1 == x1 && x1 > 0)
return x1;
else if ((int)x2 == x2 && x2 > 0)
return x2;
else
return -1;
}
// Roots are equal
else if (d == 0) {
// roots of equation
double x1 = (-b / (2 * a));
if ((int)x1 == x1 && x1 > 0)
return x1;
else
return -1;
}
// Root are imaginary
else
return -1;
}
// Driver Code
public static void Main(string[] args)
{
// K is number of diagonals
int K = 9;
// Function call
Console.Write(findRoots(K));
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript program for the above approach
// Function to find the roots of quadratic equation
function findRoots(K)
{
let a = 1;
let b = -3;
let c = -2 * K;
// Finding discriminant
let d = b * b - 4 * a * c;
let sqrt_val = Math.sqrt(Math.abs(d));
// Root are distinct
if (d > 0)
{
// roots of equation
let x1 = (-b + sqrt_val) / (2 * a);
let x2 = (-b - sqrt_val) / (2 * a);
if (Math.floor(x1) == x1 && x1 > 0)
return (Math.floor(x1));
else if (Math.floor(x2) == x2 && x2 > 0)
return (Math.floor(x2));
else
return -1;
}
// Roots are equal
else if (d == 0)
{
// roots of equation
let x1 = (-b / (2 * a));
if (Math.floor(x1) == x1 && x1 > 0)
return (Math.floor(x1));
else
return -1;
}
// Root are imaginary
else
return -1;
}
// Driver code
// K is number of diagonals
let K = 9;
// Function call
document.write(findRoots(K));
// This code is contributed by shinjanpatra
</script>
6
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Atul_kumar_Shrivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA