Count of integers up to N which represent a Binary number
Given an integer N, the task is to count every number i from 1 to N (both inclusive) such that i is a binary representation of some integer where N can be any value within the range[1, 109]
Examples:
Input: N = 100
Output: 4
Explanation: Valid integers are 1, 10, 11, 100Input: N = 20
Output: 3
Explanation: Valid integers are 1, 10, 11
Naive approach: Since maximum number of digits in N can be 10 so store every binary combination of 10 digits and then use Binary search or upper_bound to check the largest integer in the given range of N.
Time Complexity: O(MAX + log(MAX)) where MAX = 1024 (210)
Efficient approach: We can observe that for any value of N, the maximum number of such possible representations is 2count of digits of N – 1. Hence, we need to follow the following steps:
- Extract digits of N from right to left and store the position of the current digit in a variable ctr.
- If the current digit exceeds 1, it means that maximum possible representations using ctr digits can be obtained. Thus, set answer equal to 2ctr – 1.
- Otherwise, if the current digit is 1, then add 2ctr – 1 to the answer obtained so far.
- The final value obtained after traversing all the digits gives the answer.
Below is the implementation of the above approach:
C++
// C++ Program to count the // number of integers upto N // which are of the form of // binary representations #include <bits/stdc++.h> using namespace std; // Function to return the count int countBinaries( int N) { int ctr = 1; int ans = 0; while (N > 0) { // If the current last // digit is 1 if (N % 10 == 1) { // Add 2^(ctr - 1) possible // integers to the answer ans += pow (2, ctr - 1); } // If the current digit exceeds 1 else if (N % 10 > 1) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = pow (2, ctr) - 1; } ctr++; N /= 10; } return ans; } // Driver Code int main() { int N = 20; cout << countBinaries(N); return 0; } |
Java
// Java program to count the number // of integers upto N which are of // the form of binary representations import java.util.*; class GFG{ // Function to return the count static int countBinaries( int N) { int ctr = 1 ; int ans = 0 ; while (N > 0 ) { // If the current last // digit is 1 if (N % 10 == 1 ) { // Add 2^(ctr - 1) possible // integers to the answer ans += Math.pow( 2 , ctr - 1 ); } // If the current digit exceeds 1 else if (N % 10 > 1 ) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = ( int ) (Math.pow( 2 , ctr) - 1 ); } ctr++; N /= 10 ; } return ans; } // Driver Code public static void main(String[] args) { int N = 20 ; System.out.print(countBinaries(N)); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 program to count the # number of integers upto N # which are of the form of # binary representations from math import * # Function to return the count def countBinaries(N): ctr = 1 ans = 0 while (N > 0 ): # If the current last # digit is 1 if (N % 10 = = 1 ): # Add 2^(ctr - 1) possible # integers to the answer ans + = pow ( 2 , ctr - 1 ) # If the current digit exceeds 1 elif (N % 10 > 1 ): # Set answer as 2^ctr - 1 # as all possible binary # integers with ctr number # of digits can be obtained ans = pow ( 2 , ctr) - 1 ctr + = 1 N / / = 10 return ans # Driver Code if __name__ = = '__main__' : N = 20 print ( int (countBinaries(N))) # This code is contributed by Bhupendra_Singh |
C#
// C# program to count the number // of integers upto N which are of // the form of binary representations using System; class GFG{ // Function to return the count static int countBinaries( int N) { int ctr = 1; int ans = 0; while (N > 0) { // If the current last // digit is 1 if (N % 10 == 1) { // Add 2^(ctr - 1) possible // integers to the answer ans += ( int )Math.Pow(2, ctr - 1); } // If the current digit exceeds 1 else if (N % 10 > 1) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = ( int )(Math.Pow(2, ctr) - 1); } ctr++; N /= 10; } return ans; } // Driver Code public static void Main(String[] args) { int N = 20; Console.Write(countBinaries(N)); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript Program to count the // number of integers upto N // which are of the form of // binary representations // Function to return the count function countBinaries(N) { let ctr = 1; let ans = 0; while (N > 0) { // If the current last // digit is 1 if (N % 10 == 1) { // Add 2^(ctr - 1) possible // integers to the answer ans += Math.pow(2, ctr - 1); } // If the current digit exceeds 1 else if (N % 10 > 1) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = Math.pow(2, ctr) - 1; } ctr++; N /= 10; } return ans; } let N = 20; document.write(countBinaries(N)); // This code is contributed by divyesh072019. </script> |
3
Time Complexity: O(M2) where M is the count of digits in N
Auxiliary Space: O(1)
Optimization: The above approach can be optimized by pre-computing the powers of 2 up to M (count of digits up to M of N) by the help of a prefix product array.
Below is the implementation of the optimized solution:
C++
// C++ Program to count the // number of integers upto N // which are of the form of // binary representations #include <bits/stdc++.h> using namespace std; // Function to return the count int countBinaries( int N) { // PreCompute and store // the powers of 2 vector< int > powersOfTwo(11); powersOfTwo[0] = 1; for ( int i = 1; i < 11; i++) { powersOfTwo[i] = powersOfTwo[i - 1] * 2; } int ctr = 1; int ans = 0; while (N > 0) { // If the current last // digit is 1 if (N % 10 == 1) { // Add 2^(ctr - 1) possible // integers to the answer ans += powersOfTwo[ctr - 1]; } // If the current digit exceeds 1 else if (N % 10 > 1) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = powersOfTwo[ctr] - 1; } ctr++; N /= 10; } return ans; } // Driver Code int main() { int N = 20; cout << countBinaries(N); return 0; } |
Java
// Java program to count the number of // integers upto N which are of the // form of binary representations import java.util.*; class GFG{ // Function to return the count static int countBinaries( int N) { // PreCompute and store // the powers of 2 Vector<Integer> powersOfTwo = new Vector<Integer>( 11 ); powersOfTwo.add( 1 ); for ( int i = 1 ; i < 11 ; i++) { powersOfTwo.add(powersOfTwo.get(i - 1 ) * 2 ); } int ctr = 1 ; int ans = 0 ; while (N > 0 ) { // If the current last // digit is 1 if (N % 10 == 1 ) { // Add 2^(ctr - 1) possible // integers to the answer ans += powersOfTwo.get(ctr - 1 ); } // If the current digit exceeds 1 else if (N % 10 > 1 ) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = powersOfTwo.get(ctr) - 1 ; } ctr++; N /= 10 ; } return ans; } // Driver Code public static void main(String[] args) { int N = 20 ; System.out.print(countBinaries(N)); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 program to count the # number of integers upto N # which are of the form of # binary representations # Function to return the count def countBinaries(N): # PreCompute and store # the powers of 2 powersOfTwo = [ 0 ] * 11 powersOfTwo[ 0 ] = 1 for i in range ( 1 , 11 ): powersOfTwo[i] = powersOfTwo[i - 1 ] * 2 ctr = 1 ans = 0 while (N > 0 ): # If the current last # digit is 1 if (N % 10 = = 1 ): # Add 2^(ctr - 1) possible # integers to the answer ans + = powersOfTwo[ctr - 1 ] # If the current digit exceeds 1 elif (N % 10 > 1 ): # Set answer as 2^ctr - 1 # as all possible binary # integers with ctr number # of digits can be obtained ans = powersOfTwo[ctr] - 1 ctr + = 1 N = N / / 10 return ans # Driver code N = 20 print (countBinaries(N)) # This code is contributed by divyeshrabadiya07 |
C#
// C# program to count the number of // integers upto N which are of the // form of binary representations using System; using System.Collections.Generic; class GFG{ // Function to return the count static int countBinaries( int N) { // PreCompute and store // the powers of 2 List< int > powersOfTwo = new List< int >(); powersOfTwo.Add(1); for ( int i = 1; i < 11; i++) { powersOfTwo.Add(powersOfTwo[i - 1] * 2); } int ctr = 1; int ans = 0; while (N > 0) { // If the current last // digit is 1 if (N % 10 == 1) { // Add 2^(ctr - 1) possible // integers to the answer ans += powersOfTwo[ctr - 1]; } // If the current digit exceeds 1 else if (N % 10 > 1) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = powersOfTwo[ctr] - 1; } ctr++; N /= 10; } return ans; } // Driver Code static public void Main () { int N = 20; Console.Write(countBinaries(N)); } } // This code is contributed by ShubhamCoder |
Javascript
<script> // Javascript program to count the number of // integers upto N which are of the // form of binary representations // Function to return the count function countBinaries(N) { // PreCompute and store // the powers of 2 let powersOfTwo = []; powersOfTwo.push(1); for (let i = 1; i < 11; i++) { powersOfTwo.push(powersOfTwo[i - 1] * 2); } let ctr = 1; let ans = 0; while (N > 0) { // If the current last // digit is 1 if (N % 10 == 1) { // Add 2^(ctr - 1) possible // integers to the answer ans += powersOfTwo[ctr - 1]; } // If the current digit exceeds 1 else if (N % 10 > 1) { // Set answer as 2^ctr - 1 // as all possible binary // integers with ctr number // of digits can be obtained ans = powersOfTwo[ctr] - 1; } ctr++; N /= 10; } return ans; } let N = 20; document.write(countBinaries(N)); </script> |
3
Time Complexity: O(M)
Auxiliary Space: O(M)
Contact Us