Dado un número entero N , la tarea es contar cada número i desde 1 hasta N (ambos inclusive) de modo que i sea una representación binaria de algún número entero donde N puede ser cualquier valor dentro del rango [1, 10 9 ]
Ejemplos:
Entrada: N = 100
Salida: 4
Explicación: Los enteros válidos son 1, 10, 11, 100Entrada: N = 20
Salida: 3
Explicación: Los enteros válidos son 1, 10, 11
Enfoque ingenuo: dado que el número máximo de dígitos en N puede ser 10, almacene cada combinación binaria de 10 dígitos y luego use la búsqueda binaria o upper_bound para verificar el entero más grande en el rango dado de N.
Complejidad de tiempo: O(MAX + log(MAX)) donde MAX = 1024 (2 10 )
Enfoque eficiente: podemos observar que para cualquier valor de N, el número máximo de tales representaciones posibles es 2 recuento de dígitos de N – 1 . Por lo tanto, debemos seguir los siguientes pasos:
- Extrae dígitos de N de derecha a izquierda y almacena la posición del dígito actual en una variable ctr .
- Si el dígito actual excede 1, significa que se pueden obtener las máximas representaciones posibles usando dígitos ctr . Por lo tanto, establezca la respuesta igual a 2 ctr – 1 .
- De lo contrario, si el dígito actual es 1, agregue 2 ctr – 1 a la respuesta obtenida hasta ahora.
- El valor final obtenido después de atravesar todos los dígitos da la respuesta.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3
Complejidad de Tiempo: O(M 2 ) donde M es el conteo de dígitos en N
Espacio Auxiliar: O(1)
Optimización: el enfoque anterior se puede optimizar calculando previamente las potencias de 2 hasta M (recuento de dígitos hasta M de N) con la ayuda de una array de productos de prefijos.
A continuación se muestra la implementación de la solución optimizada:
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>
Producción:
3
Tiempo Complejidad: O(M)
Espacio Auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA