Check if binary representations of 0 to N are present as substrings in given binary string | C ++ program for the above approach ; Function to convert decimal to binary representation ; Iterate over all bits of N ; If bit is 1 ; Return binary representation ; Function to check if binary conversion of numbers from N to 1 exists in the string as a substring or not ; To store the count of number exists as a substring ; Traverse from N to 1 ; If current number is not present in map ; Store current number ; Find binary of t ; If the string s is a substring of str ; Mark t as true ; Increment the count ; Update for t / 2 ; Special judgment '0' ; If the count is N + 1 , return " yes " ; Driver Code ; Given String ; Given Number ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; string decimalToBinary ( int N ) { string ans = " " ; while ( N > 0 ) { if ( N & 1 ) { ans = '1' + ans ; } else { ans = '0' + ans ; } N /= 2 ; } return ans ; } string checkBinaryString ( string & str , int N ) { int map [ N + 10 ] , cnt = 0 ; memset ( map , 0 , sizeof ( map ) ) ; for ( int i = N ; i > 0 ; i -- ) { if ( ! map [ i ] ) { int t = i ; string s = decimalToBinary ( t ) ; if ( str . find ( s ) != str . npos ) { while ( t && ! map [ t ] ) { map [ t ] = 1 ; cnt ++ ; t >>= 1 ; } } } } for ( int i = 0 ; i < str . length ( ) ; i ++ ) { if ( str [ i ] == '0' ) { cnt ++ ; break ; } } if ( cnt == N + 1 ) return " True " ; else return " False " ; } int main ( ) { string str = "0110" ; int N = 3 ; cout << checkBinaryString ( str , N ) ; return 0 ; }