Number of sides of Polygon when maximum possible number of diagonals is given
Given a number K which is the maximum possible number of diagonals in any polygon, the task is to find the number of sides of that polygon.
Examples:
Input: 2
Output: 4
Explanation: A quadrilateral has 2 diagonals at max.Input: 6
Output: -1
Explanation: No polygon has at most 6 diagonals.
Approach: This problem can be solved based on the following mathematical observation:
Intuition:
for an n-sided convex polygon, from each vertex, we can draw (n β 3) diagonals.
Following this way for n-vertices, there will be n*(n β 3) diagonals but each diagonal is calculated twice.
So the total number of diagonals become n*(n β 3)/2Therefore:
n*(n β 3) / 2 = K
n*(n β 3) β 2 *K = 0
n2 β 3*n -2*K = 0
When this is compared with the general representation of quadratic equation (ax2 + bx + c)
a = 1, b = -3, c = -2 *K
for this equation.Solve the equation to get the value of n which is:
n = (-b Β± β(b2 β 4ac) )/ 2a
Follow the steps mentioned below to implement the idea:
- Use the formula derived above to find the value of n:
- The discriminant d = b2 β 4ac
- If d > 0: roots will be distinct and one of the positive roots will be the answer
- If d == 0: roots will be equal and that will be the answer
- If d < 0: roots will be imaginary and answer does not exist
Below is the implementation of the above approach:
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
Time Complexity: O(1)
Auxiliary Space: O(1)