Dado un límite N, necesitamos averiguar la cantidad de números de dígitos binarios que son más pequeños que N. Los números de dígitos binarios son aquellos números que contienen solo 0 y 1 como dígitos, como 1, 10, 101, etc. son números de dígitos binarios .
Ejemplos:
Input : N = 200 Output : 7 Count of binary digit number smaller than N is 7, enumerated below, 1, 10, 11, 110, 101, 100, 111
Una forma sencilla de resolver este problema es pasar del 1 al N y verificar cada número si es un número de dígito binario o no. Si se trata de un número de dígitos binarios, aumente la cuenta de dichos números, pero este procedimiento llevará O(N) tiempo. Podemos hacerlo mejor, ya que sabemos que el recuento de tales números será mucho más pequeño que N. Podemos iterar solo sobre números de dígitos binarios y verificar si los números generados son más pequeños que N o no.
En el siguiente código, se implementa el enfoque similar a BFS para iterar solo sobre números de dígitos binarios. Comenzamos con 1 y cada vez empujaremos (t*10) y (t*10 + 1) en la cola donde t es el elemento emergente. Si t es un número de dígito binario, entonces (t*10) y (t*10 + 1) también serán números, por lo que iteraremos sobre estos números usando solo la cola. Dejaremos de empujar elementos en la cola cuando el número emergente cruce la N.
C++
// C++ program to count all binary digit
// numbers smaller than N
#include <bits/stdc++.h>
using namespace std;
// method returns count of binary digit
// numbers smaller than N
int countOfBinaryNumberLessThanN(int N)
{
// queue to store all intermediate binary
// digit numbers
queue<int> q;
// binary digits start with 1
q.push(1);
int cnt = 0;
int t;
// loop until we have element in queue
while (!q.empty())
{
t = q.front();
q.pop();
// push next binary digit numbers only if
// current popped element is N
if (t <= N)
{
cnt++;
// uncomment below line to print actual
// number in sorted order
// cout << t << " ";
q.push(t * 10);
q.push(t * 10 + 1);
}
}
return cnt;
}
// Driver code to test above methods
int main()
{
int N = 200;
cout << countOfBinaryNumberLessThanN(N);
return 0;
}
Java
import java.util.LinkedList;
import java.util.Queue;
// java program to count all binary digit
// numbers smaller than N
public class GFG {
// method returns count of binary digit
// numbers smaller than N
static int countOfBinaryNumberLessThanN(int N) {
// queue to store all intermediate binary
// digit numbers
Queue<Integer> q = new LinkedList<>();
// binary digits start with 1
q.add(1);
int cnt = 0;
int t;
// loop until we have element in queue
while (q.size() > 0) {
t = q.peek();
q.remove();
// push next binary digit numbers only if
// current popped element is N
if (t <= N) {
cnt++;
// uncomment below line to print actual
// number in sorted order
// cout << t << " ";
q.add(t * 10);
q.add(t * 10 + 1);
}
}
return cnt;
}
// Driver code to test above methods
static public void main(String[] args) {
int N = 200;
System.out.println(countOfBinaryNumberLessThanN(N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to count all binary digit # numbers smaller than N from collections import deque # method returns count of binary digit # numbers smaller than N def countOfBinaryNumberLessThanN(N): # queue to store all intermediate binary # digit numbers q = deque() # binary digits start with 1 q.append(1) cnt = 0 # loop until we have element in queue while (q): t = q.popleft() # push next binary digit numbers only if # current popped element is N if (t <= N): cnt = cnt + 1 # uncomment below line to print actual # number in sorted order q.append(t * 10) q.append(t * 10 + 1) return cnt # Driver code to test above methods if __name__=='__main__': N = 200 print(countOfBinaryNumberLessThanN(N)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to count all binary digit
// numbers smaller than N
using System;
using System.Collections.Generic;
class GFG
{
// method returns count of binary digit
// numbers smaller than N
static int countOfBinaryNumberLessThanN(int N)
{
// queue to store all intermediate binary
// digit numbers
Queue<int> q = new Queue<int>();
// binary digits start with 1
q.Enqueue(1);
int cnt = 0;
int t;
// loop until we have element in queue
while (q.Count > 0)
{
t = q.Peek();
q.Dequeue();
// push next binary digit numbers only if
// current popped element is N
if (t <= N)
{
cnt++;
// uncomment below line to print actual
// number in sorted order
q.Enqueue(t * 10);
q.Enqueue(t * 10 + 1);
}
}
return cnt;
}
// Driver code
static void Main()
{
int N = 200;
Console.WriteLine(countOfBinaryNumberLessThanN(N));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to count all binary digit
// numbers smaller than N
// method returns count of binary digit
// numbers smaller than N
function countOfBinaryNumberLessThanN($N)
{
// queue to store all intermediate
// binary digit numbers
$q = array();
// binary digits start with 1
array_push($q, 1);
$cnt = 0;
$t = 0;
// loop until we have element in queue
while (!empty($q))
{
$t = array_pop($q);
// push next binary digit numbers only
// if current popped element is N
if ($t <= $N)
{
$cnt++;
// uncomment below line to print
// actual number in sorted order
// cout << t << " ";
array_push($q, $t * 10);
array_push($q, ($t * 10 + 1));
}
}
return $cnt;
}
// Driver Code
$N = 200;
echo countOfBinaryNumberLessThanN($N);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to count all binary digit
// numbers smaller than N
// method returns count of binary digit
// numbers smaller than N
function countOfBinaryNumberLessThanN(N) {
// queue to store all intermediate binary
// digit numbers
var q = [];
// binary digits start with 1
q.push(1);
var cnt = 0;
var t;
// loop until we have element in queue
while (q.length > 0) {
t = q.pop();
// push next binary digit numbers only if
// current popped element is N
if (t <= N) {
cnt++;
// uncomment below line to print actual
// number in sorted order
q.push(t * 10);
q.push(t * 10 + 1);
}
}
return cnt;
}
// Driver code
var N = 200;
document.write(countOfBinaryNumberLessThanN(N) + "<br>");
</script>
Producción:
7
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA