Count of integers up to N which represent a Binary number

0 0 8 minutes read

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, 10⁹]

Examples:

Input: N = 100
Output: 4
Explanation: Valid integers are 1, 10, 11, 100

Input: 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 (2¹⁰)

Efficient approach: We can observe that for any value of N, the maximum number of such possible representations is 2^{count 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 2^ctr – 1.
Otherwise, if the current digit is 1, then add 2^{ctr – 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>

Output:

Time Complexity: O(M²) 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>

Output:

Time Complexity: O(M)
Auxiliary Space: O(M)

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 zambiatek!