Given a positive integer n, the task is to check if it is a Thabit number. If the given number is a Thabit number then print ‘YES’ otherwise print ‘NO’.
Thabit number: In mathematics, a Thabit Number is a positive integer of form 3* 2n – 1, where n is a non-negative integer.
The first few Thabit numbers are –
2, 5, 11, 23, 47, 95, 191, 383, 767, 1535, 3071, 6143, 12287, 24575, 49151, 98303, 196607, 393215,
Examples:
Input: 47
Output: YES
Explanation: for n=4, 47 can be expressed in the form of 3.2n -1 as 3.24 -1.Input: 65
Output: NO
Explanation: No such value of n exist for which 65 can be expressed in the form of 3.2n – 1
Approach :
- Add 1 to the given number, Now the number must be of the form 3*2n
- Divide the number by 3, By now the number must be of the form 2n
- Check if the number is a power of 2 or not, To check if the number is power of two or not refer this .
- If the number is power of 2 then Print ‘YES’ otherwise ‘NO’.
C++
// CPP program to check if a given// number is Thabit number or not.#include <bits/stdc++.h>using namespace std;// Utility function to check power of twobool isPowerOfTwo(int n){ return (n && !(n & (n - 1)));}// function to check if the given number// is Thabit Numberbool isThabitNumber(int n){ // Add 1 to the number n = n + 1; // Divide the number by 3 if (n % 3 == 0) n = n / 3; else return false; // Check if the given number is power of 2 if (isPowerOfTwo(n)) return true; else return false;}// Driver Programint main(){ int n = 47; if (isThabitNumber(n)) cout << "YES"; else cout << "NO"; return 0;} |
Java
// Java code to check// for thabit numberclass GFG { // Utility function to check power of two static boolean isPowerOfTwo(int n) { return n != 0 && ((n & (n - 1)) == 0); } // function to check if the given number // is Thabit Number static boolean isThabitNumber(int n) { // Add 1 to the number n = n + 1; // Divide the number by 3 if (n % 3 == 0) n = n / 3; else return false; // Check if the given number is power of 2 if (isPowerOfTwo(n)) return true; else return false; } // Driver Program public static void main(String[] args) { int n = 47; // Check if number is // thabit number if (isThabitNumber(n)) { System.out.println("YES"); } else { System.out.println("NO"); } }} |
Python3
# Python code to check# thabit number# Utility function to Check # power of two def isPowerOfTwo(n): return (n and (not(n & (n - 1)))) # function to check if the given number# is Thabit Numberdef isThabitNumber( n ): # Add 1 to the number n = n + 1; # Divide the number by 3 if (n % 3 == 0): n = n//3; else: return False # Check if the given number # is power of 2 if (isPowerOfTwo(n)): return True else: return False # Driver Program n = 47# Check if number is # thabit number if (isThabitNumber(n)): print("YES")else: print("NO") |
C#
// C# code to check// thabit numberusing System;class GFG { // Utility function to check power of two static bool isPowerOfTwo(int n) { return n != 0 && ((n & (n - 1)) == 0); } // function to check if the given number // is Thabit Number static bool isThabitNumber(int n) { // Add 1 to the number n = n + 1; // Divide the number by 3 if (n % 3 == 0) n = n / 3; else return false; // Check if the given number is power of 2 if (isPowerOfTwo(n)) return true; else return false; } // Driver Program public static void Main() { int n = 47; // Check if number is // thabit number if (isThabitNumber(n)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
PHP
<?php// PHP program to check if a given// number is Thabit number or not.// Utility function to check// power of twofunction isPowerOfTwo($n){ return ($n && !($n & ($n - 1)));}// function to check if the // given number is Thabit Numberfunction isThabitNumber($n){ // Add 1 to the number $n = $n + 1; // Divide the number by 3 if ($n % 3 == 0) $n = $n / 3; else return false; // Check if the given number // is power of 2 if (isPowerOfTwo($n)) return true; else return false;}// Driver Code$n = 47;if (isThabitNumber($n)) echo "YES"; else echo "NO"; // This code is contributed// by Shashank?> |
Javascript
<script>// Javascript program to check if a given// number is Thabit number or not.// Utility function to check power of twofunction isPowerOfTwo(n){ return (n && !(n & (n - 1)));}// function to check if the given number// is Thabit Numberfunction isThabitNumber(n){ // Add 1 to the number n = n + 1; // Divide the number by 3 if (n % 3 == 0) n = n / 3; else return false; // Check if the given number is power of 2 if (isPowerOfTwo(n)) return true; else return false;}// Driver Programvar n = 47;if (isThabitNumber(n)) document.write( "YES"); else document.write("NO"); </script> |
Output:
YES
Time Complexity: O(1), as only constant operations are performed.
Auxiliary Space: O(1) as no extra space is used.
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!