Binary Search
Binary search to find if the given number N matches any Heptagonal Number. This approach is more efficient than brute
force as it reduces the search space by half at each iteration.
Below is code implementation of the above approach:
C++
#include <iostream> using namespace std; // Function to check if a number is a Heptagonal number string isHeptagonal( int n) { int left = 1; int right = n; while (left <= right) { int mid = (left + right) / 2; // Calculate the Heptagonal Number using the formula int hn = mid * (5 * mid - 3) / 2; if (hn == n) { return "Yes" ; // If the number is Heptagonal, return "Yes" } else if (hn < n) { left = mid + 1; // If the calculated Heptagonal number is less than the input, move to the right half } else { right = mid - 1; // If the calculated Heptagonal number is greater than the input, move to the left half } } return "No" ; // If the number is not Heptagonal, return "No" } int main() { cout << isHeptagonal(7) << endl; // Check if 7 is a Heptagonal number return 0; } |
Java
public class GFG { static String isHeptagonal( int n) { int left = 1 ; int right = n; while (left <= right) { int mid = (left + right) / 2 ; // Calculate the Heptagonal Number using the formula int hn = mid * ( 5 * mid - 3 ) / 2 ; if (hn == n) { return "Yes" ; } else if (hn < n) { left = mid + 1 ; } else { right = mid - 1 ; } } return "No" ; } public static void main(String[] args) { System.out.println(isHeptagonal( 7 )); } } |
Python
def is_heptagonal(n): left = 1 right = n while left < = right: mid = (left + right) / / 2 # Calculate the Heptagonal Number using the formula hn = mid * ( 5 * mid - 3 ) / / 2 if hn = = n: return "Yes" elif hn < n: left = mid + 1 else : right = mid - 1 return "No" # Test the function print (is_heptagonal( 7 )) |
C#
using System; class Program { // Function to check if a number is a Heptagonal number static string IsHeptagonal( int n) { int left = 1; int right = n; while (left <= right) { int mid = (left + right) / 2; // Calculate the Heptagonal Number using the formula int hn = mid * (5 * mid - 3) / 2; if (hn == n) { return "Yes" ; // If the number is Heptagonal, return "Yes" } else if (hn < n) { left = mid + 1; // If the calculated Heptagonal number is less than the input, move to the right half } else { right = mid - 1; // If the calculated Heptagonal number is greater than the input, move to the left half } } return "No" ; // If the number is not Heptagonal, return "No" } static void Main() { Console.WriteLine(IsHeptagonal(7)); // Check if 7 is a Heptagonal number } } |
Javascript
function isHeptagonal(n) { let left = 1; let right = n; while (left <= right) { let mid = Math.floor((left + right) / 2); // Calculate the Heptagonal Number using the formula let hn = mid * (5 * mid - 3) / 2; if (hn === n) { return "Yes" ; } else if (hn < n) { left = mid + 1; } else { right = mid - 1; } } return "No" ; } // Test the function console.log(isHeptagonal(7)); |
Output
Yes
Time Complexity: O(log n)
Auxiliary Space: O(1)
Program to check if N is a Heptagonal Number
Given an integer N, the task is to check if N is a Heptagonal Number or not. If the number N is an Heptagonal Number then print “Yes” else print “No”.
Heptagonal Number represents Heptagon and belongs to a figurative number. Heptagonal has seven angles, seven vertices, and seven-sided polygon. The first few Heptagonal Numbers are 1, 7, 18, 34, 55, 81, …
Examples:
Input: N = 7
Output: Yes
Explanation:
Second heptagonal number is 7.Input: N = 30
Output: No
Approach:
- The Kth term of the heptagonal number is given as
- As we have to check that the given number can be expressed as a Heptagonal Number or not. This can be checked as:
=>
=>
- If the value of K calculated using the above formula is an integer, then N is a Heptagonal Number.
- Else N is not a Heptagonal Number.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if N is a // Heptagonal number bool isheptagonal( int N) { float n = (3 + sqrt (40 * N + 9)) / 10; // Condition to check if the // number is a heptagonal number return (n - ( int )n) == 0; } // Driver Code int main() { // Given Number int N = 7; // Function call if (isheptagonal(N)) { cout << "Yes" ; } else { cout << "No" ; } return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to check if N // is a heptagonal number public static boolean isheptagonal( int N) { double n = ( 3 + Math.sqrt( 40 * N + 9 )) / 10 ; // Condition to check if the number // is a heptagonal number return (n - ( int )n) == 0 ; } // Driver code public static void main(String[] args) { // Given Number int N = 7 ; // Function call if (isheptagonal(N)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by coder001 |
Python3
# Python3 program for the above approach import math # Function to check if N is a # heptagonal number def isheptagonal(N): n = ( 3 + math.sqrt( 40 * N + 9 )) / 10 # Condition to check if the # number is a heptagonal number return (n - int (n)) = = 0 # Driver Code N = 7 # Function call if (isheptagonal(N)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Shubham_Coder |
C#
// C# program for the above approach using System; class GFG { // Function to check if N // is a heptagonal number public static bool isheptagonal( int N) { double n = (3 + Math.Sqrt(40 * N + 9)) / 10; // Condition to check if the number // is a heptagonal number return (n - ( int )n) == 0; } // Driver code public static void Main(String[] args) { // Given Number int N = 7; // Function call if (isheptagonal(N)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript program for the above approach // Function to check if N is a // Heptagonal number function isheptagonal(N) { var n = (3 + Math.sqrt(40 * N + 9)) / 10; // Condition to check if the // number is a heptagonal number return (n - parseInt(n)) == 0; } // Given Number var N = 7; // Function call if (isheptagonal(N)) { document.write( "Yes" ); } else { document.write( "No" ); } </script> |
Output
Yes
Time complexity: O(logN) because it is using inbuilt sqrt function
Auxiliary Space: O(1)