Given a positive integer N, the task is to check whether the binary equivalent of that integer ends with “001” or not.
Print “Yes” if it ends in “001”. Otherwise, Print “No“.
Examples :
Input: N = 9
Output: Yes
Explanation Binary of 9 = 1001, which ends with 001
Input: N = 5
Output: No
Binary of 5 = 101, which does not end in 001
Naive Approach
Find the Binary Equivalent of N and check if 001 is a Suffix of its Binary Equivalent.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool isSuffix(string s1,
string s2)
{
int n1 = s1.length();
int n2 = s2.length();
if (n1 > n2)
return false ;
for ( int i = 0; i < n1; i++)
if (s1[n1 - i - 1]
!= s2[n2 - i - 1])
return false ;
return true ;
}
bool CheckBinaryEquivalent( int N)
{
int B_Number = 0;
int cnt = 0;
while (N != 0) {
int rem = N % 2;
int c = pow (10, cnt);
B_Number += rem * c;
N /= 2;
cnt++;
}
string bin = to_string(B_Number);
return isSuffix( "001" , bin);
}
int main()
{
int N = 9;
if (CheckBinaryEquivalent(N))
cout << "Yes" ;
else
cout << "No" ;
return 0;
}
|
Java
class GFG{
static boolean isSuffix(String s1, String s2)
{
int n1 = s1.length();
int n2 = s2.length();
if (n1 > n2)
return false ;
for ( int i = 0 ; i < n1; i++)
if (s1.charAt(n1 - i - 1 ) !=
s2.charAt(n2 - i - 1 ))
return false ;
return true ;
}
static boolean CheckBinaryEquivalent( int N)
{
int B_Number = 0 ;
int cnt = 0 ;
while (N != 0 )
{
int rem = N % 2 ;
int c = ( int )Math.pow( 10 , cnt);
B_Number += rem * c;
N /= 2 ;
cnt++;
}
String bin = Integer.toString(B_Number);
return isSuffix( "001" , bin);
}
public static void main (String[] args)
{
int N = 9 ;
if (CheckBinaryEquivalent(N))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}
|
Python3
def isSuffix(s1, s2) :
n1 = len (s1);
n2 = len (s2);
if (n1 > n2) :
return False ;
for i in range (n1) :
if (s1[n1 - i - 1 ] ! = s2[n2 - i - 1 ]) :
return False ;
return True ;
def CheckBinaryEquivalent(N) :
B_Number = 0 ;
cnt = 0 ;
while (N ! = 0 ) :
rem = N % 2 ;
c = 10 * * cnt;
B_Number + = rem * c;
N / / = 2 ;
cnt + = 1 ;
bin = str (B_Number);
return isSuffix( "001" , bin );
if __name__ = = "__main__" :
N = 9 ;
if (CheckBinaryEquivalent(N)) :
print ( "Yes" );
else :
print ( "No" );
|
C#
using System;
class GFG{
static bool isSuffix( string s1, string s2)
{
int n1 = s1.Length;
int n2 = s2.Length;
if (n1 > n2)
return false ;
for ( int i = 0; i < n1; i++)
if (s1[n1 - i - 1] !=
s2[n2 - i - 1])
return false ;
return true ;
}
static bool CheckBinaryEquivalent( int N)
{
int B_Number = 0;
int cnt = 0;
while (N != 0)
{
int rem = N % 2;
int c = ( int )Math.Pow(10, cnt);
B_Number += rem * c;
N /= 2;
cnt++;
}
string bin = B_Number.ToString();
return isSuffix( "001" , bin);
}
public static void Main ( string [] args)
{
int N = 9;
if (CheckBinaryEquivalent(N))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}
|
Javascript
<script>
function isSuffix( s1, s2)
{
var n1 = s1.length;
var n2 = s2.length;
if (n1 > n2)
return false ;
for ( var i = 0; i < n1; i++)
if (s1[n1 - i - 1] !=
s2[n2 - i - 1])
return false ;
return true ;
}
function CheckBinaryEquivalent( N)
{
var B_Number = 0;
var cnt = 0;
while (N != 0)
{
var rem = N % 2;
var c = Math.pow(10, cnt);
B_Number += rem * c;
N = Math.floor(N/ 2);
cnt++;
}
console.log(B_Number);
var bin = B_Number.toString();
return isSuffix( "001" , bin);
}
var N = 9;
if (CheckBinaryEquivalent(N))
document.write( "Yes" );
else
document.write( "No" );
</script>
|
Time complexity: O(N)
Auxiliary space: O(1)
Efficient Approach
We can observe that the binary equivalent of a number ends in “001” only when (N – 1) is divisible by 8.
Illustration:
The sequence 1, 9, 17, 25, 33……. has 001 as the suffix in their binary representation.
Nth term of the above sequence is denoted by 8 * N + 1
So the binary equivalent of a number ends in “001” only when (N – 1) % 8 == 0
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool CheckBinaryEquivalent( int N)
{
return (N - 1) % 8 == 0;
}
int main()
{
int N = 9;
if (CheckBinaryEquivalent(N))
cout << "Yes" ;
else
cout << "No" ;
return 0;
}
|
Java
class GFG{
static boolean CheckBinaryEquivalent( int N)
{
return (N - 1 ) % 8 == 0 ;
}
public static void main (String[] args)
{
int N = 9 ;
if (CheckBinaryEquivalent(N))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}
|
Python3
def CheckBinaryEquivalent(N):
return (N - 1 ) % 8 = = 0 ;
if __name__ = = "__main__" :
N = 9 ;
if (CheckBinaryEquivalent(N)):
print ( "Yes" );
else :
print ( "No" );
|
C#
using System;
class GFG{
static bool CheckBinaryEquivalent( int N)
{
return (N - 1) % 8 == 0;
}
public static void Main ( string [] args)
{
int N = 9;
if (CheckBinaryEquivalent(N))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}
|
Javascript
<script>
function CheckBinaryEquivalent(N)
{
return (N - 1) % 8 == 0;
}
var N = 9;
if (CheckBinaryEquivalent(N))
document.write( "Yes" );
else
document.write( "No" );
</script>
|
Time complexity: O(1)
Auxiliary space: O(1)
Bitwise Approach
if any no. N has (001)2 at the end in its binary representation then N-1 has (000)2 at the end in its binary representation then doing its bitwise and with 7 (111)2 will give you (000)2 as result.
so simple return !((N – 1) & 7)
C++
#include <bits/stdc++.h>
using namespace std;
bool CheckBinaryEquivalent( int N)
{
return !((N - 1) & 7);
}
int main()
{
int N = 9;
if (CheckBinaryEquivalent(N))
cout << "Yes" ;
else
cout << "No" ;
return 0;
}
|
Java
class GFG {
static boolean CheckBinaryEquivalent( int N)
{
if (((N - 1 ) & 7 ) > 0 )
return false ;
else
return true ;
}
public static void main(String[] args)
{
int N = 9 ;
if (CheckBinaryEquivalent(N))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}
|
Python3
def CheckBinaryEquivalent(N):
return ( not ((N - 1 ) & 7 ))
N = 9
if (CheckBinaryEquivalent(N)):
print ( "Yes" )
else :
print ( "No" )
|
C#
using System;
class GFG {
static bool CheckBinaryEquivalent( int N)
{
if (((N - 1) & 7) > 0)
return false ;
else
return true ;
}
public static void Main( string [] args)
{
int N = 9;
if (CheckBinaryEquivalent(N))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}
|
Javascript
function CheckBinaryEquivalent(N)
{
return !((N - 1) & 7);
}
let N = 9;
if (CheckBinaryEquivalent(N))
console.log( "Yes" );
else
console.log( "No" );
|
Time Complexity: O(1)
Auxiliary Space : O(1)
Method:
1. In this method, we convert the input number to its binary representation using the bin() function, which returns a string prefixed with “0b”.
2. We slice off the “0b” prefix by starting the string slice at index 2, and then slice the last three characters of the resulting string using the [-3:] syntax. We compare this substring to the string “001” to check if it matches.
C++
#include <iostream>
#include <bitset>
using namespace std;
int main() {
int n = 9;
bitset<32> binary(n);
string binary_str = binary.to_string();
if (binary_str.substr(binary_str.length() - 3) == "001" ) {
cout << "The binary equivalent of " << n << " ends with 001" << endl;
} else {
cout << "The binary equivalent of " << n << " does not end with 001" << endl;
}
return 0;
}
|
Java
public class BinaryCheck {
public static void main(String[] args) {
int n = 9 ;
String binary = Integer.toBinaryString(n);
if (binary.endsWith( "001" )) {
System.out.println( "The binary equivalent of " + n + " ends with 001" );
} else {
System.out.println( "The binary equivalent of " + n + " does not end with 001" );
}
}
}
|
Python3
n = 9
binary = bin (n)[ 2 :]
if binary[ - 3 :] = = '001' :
print ( "The binary equivalent of" , n, "ends with 001" )
else :
print ( "The binary equivalent of" , n, "does not end with 001" )
|
C#
using System;
class MainClass {
public static void Main ( string [] args) {
int n = 9;
string binaryStr = Convert.ToString(n, 2);
if (binaryStr.Substring(binaryStr.Length - 3) == "001" ) {
Console.WriteLine( "The binary equivalent of " + n + " ends with 001" );
} else {
Console.WriteLine( "The binary equivalent of " + n + " does not end with 001" );
}
}
}
|
Javascript
let n = 9;
let binary = n.toString(2).padStart(32, '0' );
if (binary.substr(binary.length - 3) === "001" ) {
console.log(`The binary equivalent of ${n} ends with 001`);
} else {
console.log(`The binary equivalent of ${n} does not end with 001`);
}
|
Output
The binary equivalent of 9 ends with 001
Time Complexity: O(log n)
Auxiliary Space : O(log n)
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!