Stella Octangula Number | Program to check if a number is Stella Octangula Number ; Returns value of n * ( 2 * n * n - 1 ) ; Finds if a value of f ( n ) is equal to x where n is in interval [ low . . high ] ; Returns true if x isStella Octangula Number . Else returns false . ; Find ' high ' for binary search by repeated doubling ; If condition is satisfied for a power of 2. ; Call binary search ; driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int f ( int n ) { return n * ( 2 * n * n - 1 ) ; } bool binarySearch ( int low , int high , int x ) { while ( low <= high ) { long long mid = ( low + high ) / 2 ; if ( f ( mid ) < x ) low = mid + 1 ; else if ( f ( mid ) > x ) high = mid - 1 ; else return true ; } return false ; } bool isStellaOctangula ( int x ) { if ( x == 0 ) return true ; int i = 1 ; while ( f ( i ) < x ) i = i * 2 ; if ( f ( i ) == x ) return true ; return binarySearch ( i / 2 , i , x ) ; } int main ( ) { int n = 51 ; if ( isStellaOctangula ( n ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }