Given a regular polygon of N sides, the task is to find the maximum sided polygon that can be inscribed inside the given polygon by joining non-adjacent vertices. Print -1, if no such polygon exist.
Examples:
Input: N = 8
Output: 4
Explanation:
At most a 4 sided polygon can be inscribed inside the given 8-sided polygon as shown below:
Input: N = 3
Output: -1
Approach: The idea is to observe the fact that a regular polygon can be inscribed inside another regular polygon of N sides if N is even. Follow the below steps to solve the problem:
- If N is even, then the inscribed polygon with the maximum sides can be formed by joining the non-adjacent vertices. Therefore, print N/2 as the required answer.
- Otherwise, print -1 as no regular polygon can be inscribed inside an odd-sided polygon.
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 maximum// sided polygon that can be inscribedint MaximumSides(int n){ // Base Case if (n < 4) return -1; // Return n/2 if n is even // Otherwise, return -1 return n % 2 == 0 ? n / 2 : -1;}// Driver Codeint main(){ // Given N int N = 8; // Function Call cout << MaximumSides(N); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{// Function to find the // maximum sided polygon // that can be inscribedstatic int MaximumSides(int n){ // Base Case if (n < 4) return -1; // Return n/2 if n is // even Otherwise, return -1 return n % 2 == 0 ? n / 2 : -1;}// Driver Codepublic static void main(String[] args){ // Given N int N = 8; // Function Call System.out.print(MaximumSides(N));}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to find the maximum sided # polygon that can be inscribeddef MaximumSides(n): # Base Case if (n < 4): return -1 # Return n/2 if n is even # Otherwise, return -1 if n % 2 == 0: return n // 2 return -1# Driver Codeif __name__ == '__main__': # Given N N = 8 # Function Call print(MaximumSides(N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;class GFG{// Function to find the // maximum sided polygon // that can be inscribedstatic int MaximumSides(int n){ // Base Case if (n < 4) return -1; // Return n/2 if n is // even Otherwise, return -1 return n % 2 == 0 ? n / 2 : -1;}// Driver Codepublic static void Main(String[] args){ // Given N int N = 8; // Function Call Console.Write(MaximumSides(N));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the // above approach // Function to find the // maximum sided polygon // that can be inscribed function MaximumSides( n) { // Base Case if (n < 4) return -1; // Return n/2 if n is // even Otherwise, return -1 return n % 2 == 0 ? n / 2 : -1; } // Driver Code // Given N let N = 8; // Function Call document.write(MaximumSides(N));// This code is contributed by shikhasingrajput </script> |
Output:
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
