Given a number N, the task is to check if the binary representation of the number N has only “01” and “10” as a substring or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 5
Output: Yes
Explanation:
(5)10 is (101)2 which contains only “01” and “10” as substring.
Input: N = 11
Output: No
Explanation:
(11)10 is (1011)2 which contains only “11” a substring.
Approach: The given problem can be solved using the following observations:
- Since the substring must contain “01” and “10”. Therefore, the binary representation contains 1 and 0 alternately.
- For binary representations containing 0 and 1 alternately, the following pattern can be observed:
2, 5, 10, 21, …
- The above pattern is of the form 2 * x and (4 * x + 1) such that the last term of the series is x.
From the above observation, the idea is to generate the given series using the above pattern and check if the given number exists in the pattern or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;vector<int> Ans;// Function to generate all numbers// having "01" and "10" as a substringvoid populateNumber(){ // Insert 2 and 5 Ans.push_back(2); Ans.push_back(5); long long int x = 5; // Iterate till x is 10 ^ 15 while (x < 1000000000001) { // Multiply x by 2 x *= 2; Ans.push_back(x); // Update x as x*2 + 1 x = x * 2 + 1; Ans.push_back(x); }}// Function to check if binary representation// of N contains only "01" and "10" as substringstring checkString(long long int N){ // Function Call to generate all // such numbers populateNumber(); // Check if a number N // exists in Ans[] or not for (auto& it : Ans) { // If the number exists if (it == N) { return "Yes"; } } // Otherwise return "No";}// Driver Codeint main(){ long long int N = 5; // Function Call cout << checkString(N); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*; class GFG { static int N = 200000; static long Ans[] = new long [200000]; static int index = 0; // Function to generate all numbers // having "01" and "10" as a substring static void populateNumber() { // Insert 2 and 5 Ans[index++] = (2); Ans[index++] = (5); long x = 5; long inf = 1000000000001L; // Iterate till x is 10 ^ 15 while (x < inf) { // Multiply x by 2 x *= 2; Ans[index++] = (x); // Update x as x*2 + 1 x = x * 2 + 1; Ans[index++] = (x); } } // Function to check if binary representation // of N contains only "01" and "10" as substring static void checkString(int N) { // Function Call to generate all // such numbers populateNumber(); // Check if a number N // exists in Ans[] or not for (int i = 0; i < index; i++) { // If the number exists if (Ans[i] == N) { System.out.println("YES"); return; } } System.out.println("NO"); } // Driver Code public static void main(String[] args) { N = 5; checkString(N); }}// This code is contributed by amreshkumar3. |
Python3
# Python3 program to implement# the above approachAns = []# Function to generate all numbers# having "01" and "10" as a substringdef populateNumber() : # Insert 2 and 5 Ans.append(2) Ans.append(5) x = 5 # Iterate till x is 10 ^ 15 while (x < 1000000000001) : # Multiply x by 2 x *= 2 Ans.append(x) # Update x as x*2 + 1 x = x * 2 + 1 Ans.append(x)# Function to check if binary representation# of N contains only "01" and "10" as substringdef checkString(N) : # Function Call to generate all # such numbers populateNumber() # Check if a number N # exists in Ans[] or not for it in Ans : # If the number exists if (it == N) : return "Yes" # Otherwise return "No"# Driver CodeN = 5# Function Callprint(checkString(N))# This code is contributed by sanjoy_62 |
C#
// C# Program to implement// the above approachusing System;class GFG { static int N = 200000; static long []Ans = new long [200000]; static int index = 0; // Function to generate all numbers // having "01" and "10" as a substring static void populateNumber() { // Insert 2 and 5 Ans[index++] = (2); Ans[index++] = (5); long x = 5; long inf = 1000000000001L; // Iterate till x is 10 ^ 15 while (x < inf) { // Multiply x by 2 x *= 2; Ans[index++] = (x); // Update x as x*2 + 1 x = x * 2 + 1; Ans[index++] = (x); } } // Function to check if binary representation // of N contains only "01" and "10" as substring static void checkString(int N) { // Function Call to generate all // such numbers populateNumber(); // Check if a number N // exists in Ans[] or not for (int i = 0; i < index; i++) { // If the number exists if (Ans[i] == N) { Console.WriteLine("YES"); return; } } Console.WriteLine("NO"); } // Driver Code public static void Main(String[] args) { N = 5; checkString(N); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// javascript Program to implement// the above approach var N = 200000; var Ans = Array.from({length: N}, (_, i) => 0); var index = 0; // Function to generate all numbers // having "01" and "10" as a substring function populateNumber() { // Insert 2 and 5 Ans[index++] = (2); Ans[index++] = (5); var x = 5; var inf = 1000000000001; // Iterate till x is 10 ^ 15 while (x < inf) { // Multiply x by 2 x *= 2; Ans[index++] = (x); // Update x as x*2 + 1 x = x * 2 + 1; Ans[index++] = (x); } } // Function to check if binary representation // of N contains only "01" and "10" as substring function checkString(N) { // Function Call to generate all // such numbers populateNumber(); // Check if a number N // exists in Ans or not for (i = 0; i < index; i++) { // If the number exists if (Ans[i] == N) { document.write("YES"); return; } } document.write("NO"); } // Driver Code N = 5; checkString(N);// This code contributed by shikhasingrajput </script> |
Output:
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
