Given Q queries where each query consists of an integer N and the task is to find the smallest integer greater than N such that there are no consecutive 1s in its binary representation.
Examples:
Input: Q[] = {4, 6}
Output:
5
8Input: Q[] = {50, 23, 456}
Output:
64
32
512
Approach: Store all the numbers in a list whose binary representation does not contain consecutive 1s upto a fixed limit. Now for every given N, find the next greater element in the list generated previously using binary search.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int MAX = 100000;// To store the pre-computed integersvector<int> v;// Function that returns true if the// binary representation of x contains// consecutive 1sint consecutiveOnes(int x){ // To store the previous bit int p = 0; while (x > 0) { // Check whether the previous bit // and the current bit are both 1 if (x % 2 == 1 and p == 1) return true; // Update previous bit p = x % 2; // Go to the next bit x /= 2; } return false;}// Function to pre-compute the// valid numbers from 0 to MAXvoid preCompute(){ // Store all the numbers which do // not have consecutive 1s for (int i = 0; i <= MAX; i++) { if (!consecutiveOnes(i)) v.push_back(i); }}// Function to return the minimum// number greater than n which does// not contain consecutive 1sint nextValid(int n){ // Search for the next greater element // with no consecutive 1s int it = upper_bound(v.begin(), v.end(), n) - v.begin(); int val = v[it]; return val;}// Function to perform the queriesvoid performQueries(int queries[], int q){ for (int i = 0; i < q; i++) cout << nextValid(queries[i]) << "\n";}// Driver codeint main(){ int queries[] = { 4, 6 }; int q = sizeof(queries) / sizeof(int); // Pre-compute the numbers preCompute(); // Perform the queries performQueries(queries, q); return 0;} |
Java
// Java implementation of the approachimport java.io.*;import java.util.*;class GFG{ static int MAX = 100000;// To store the pre-computed integers static ArrayList<Integer> v = new ArrayList<Integer>();public static int upper_bound(ArrayList<Integer> ar, int k){ int s = 0; int e = ar.size(); while (s != e) { int mid = s + e >> 1; if (ar.get(mid) <= k) { s = mid + 1; } else { e = mid; } } if (s == ar.size()) { return -1; } return s;}// Function that returns true if the // binary representation of x contains // consecutive 1sstatic int consecutiveOnes(int x){ // To store the previous bit int p = 0; while (x > 0) { // Check whether the previous bit // and the current bit are both 1 if (x % 2 == 1 && p == 1) { return 1; } // Update previous bit p = x % 2; // Go to the next bit x /= 2; } return 0;}// Function to pre-compute the // valid numbers from 0 to MAX static void preCompute(){ // Store all the numbers which do // not have consecutive 1s for(int i = 0; i <= MAX; i++) { if (consecutiveOnes(i) == 0) { v.add(i); } }}// Function to return the minimum // number greater than n which does // not contain consecutive 1s static int nextValid(int n){ // Search for the next greater element // with no consecutive 1s int it = upper_bound(v,n); int val = v.get(it); return val;}// Function to perform the queries static void performQueries(int queries[], int q){ for(int i = 0; i < q; i++) { System.out.println(nextValid(queries[i])); }}// Driver code public static void main(String[] args) { int queries[] = { 4, 6 }; int q = queries.length; // Pre-compute the numbers preCompute(); // Perform the queries performQueries(queries, q);}}// This code is contributed by rag2127 |
Python3
# Python3 implementation of the approachfrom bisect import bisect_right as upper_boundMAX = 100000# To store the pre-computed integersv = []# Function that returns true if the# binary representation of x contains# consecutive 1sdef consecutiveOnes(x): # To store the previous bit p = 0 while (x > 0): # Check whether the previous bit # and the current bit are both 1 if (x % 2 == 1 and p == 1): return True # Update previous bit p = x % 2 # Go to the next bit x //= 2 return False# Function to pre-compute the# valid numbers from 0 to MAXdef preCompute(): # Store all the numbers which do # not have consecutive 1s for i in range(MAX + 1): if (consecutiveOnes(i) == 0): v.append(i)# Function to return the minimum# number greater than n which does# not contain consecutive 1sdef nextValid(n): # Search for the next greater element # with no consecutive 1s it = upper_bound(v, n) val = v[it] return val# Function to perform the queriesdef performQueries(queries, q): for i in range(q): print(nextValid(queries[i]))# Driver codequeries = [4, 6]q = len(queries)# Pre-compute the numberspreCompute()# Perform the queriesperformQueries(queries, q)# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{static int MAX = 100000;// To store the pre-computed integers static List<int> v = new List<int>();static int upper_bound(List<int> ar, int k){ int s = 0; int e = ar.Count; while (s != e) { int mid = s + e >> 1; if (ar[mid] <= k) { s = mid + 1; } else { e = mid; } } if (s == ar.Count) { return -1; } return s;}// Function that returns true if the // binary representation of x contains // consecutive 1sstatic int consecutiveOnes(int x){ // To store the previous bit int p = 0; while (x > 0) { // Check whether the previous bit // and the current bit are both 1 if (x % 2 == 1 && p == 1) { return 1; } // Update previous bit p = x % 2; // Go to the next bit x /= 2; } return 0;}// Function to pre-compute the // valid numbers from 0 to MAX static void preCompute(){ // Store all the numbers which do // not have consecutive 1s for(int i = 0; i <= MAX; i++) { if (consecutiveOnes(i) == 0) { v.Add(i); } }}// Function to return the minimum // number greater than n which does // not contain consecutive 1s static int nextValid(int n){ // Search for the next greater element // with no consecutive 1s int it = upper_bound(v, n); int val = v[it]; return val;}// Function to perform the queries static void performQueries(int[] queries, int q){ for(int i = 0; i < q; i++) { Console.WriteLine(nextValid(queries[i])); }}// Driver code static public void Main(){ int[] queries = { 4, 6 }; int q = queries.Length; // Pre-compute the numbers preCompute(); // Perform the queries performQueries(queries, q);}}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// JavaScript implementation of the approachconst MAX = 100000;// To store the pre-computed integerslet v = [];function upper_bound(ar, k){ let s = 0; let e = ar.length; while (s != e) { let mid = s + e >> 1; if (ar[mid] <= k) { s = mid + 1; } else { e = mid; } } if (s == ar.length) { return -1; } return s;}// Function that returns true if the// binary representation of x contains// consecutive 1sfunction consecutiveOnes(x){ // To store the previous bit let p = 0; while (x > 0) { // Check whether the previous bit // and the current bit are both 1 if (x % 2 == 1 && p == 1) return true; // Update previous bit p = x % 2; // Go to the next bit x = parseInt(x / 2); } return false;}// Function to pre-compute the// valid numbers from 0 to MAXfunction preCompute(){ // Store all the numbers which do // not have consecutive 1s for (let i = 0; i <= MAX; i++) { if (!consecutiveOnes(i)) v.push(i); }}// Function to return the minimum// number greater than n which does// not contain consecutive 1sfunction nextValid(n){ // Search for the next greater element // with no consecutive 1s let it = upper_bound(v, n); let val = v[it]; return val;}// Function to perform the queriesfunction performQueries(queries, q){ for (let i = 0; i < q; i++) document.write(nextValid(queries[i]) + "<br>");}// Driver code let queries = [ 4, 6 ]; let q = queries.length; // Pre-compute the numbers preCompute(); // Perform the queries performQueries(queries, q);</script> |
Output:
5 8
Time Complexity: O(MAX * log MAX)
Auxiliary Space: O(MAX)
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!
