Encuentre el número obtenido al concatenar representaciones binarias de todos los números hasta N

Dado un número entero N , la tarea es encontrar el valor decimal de la string binaria formada al concatenar las representaciones binarias de todos los números del 1 al N secuencialmente.

Ejemplos:

Entrada: N = 12
Salida: 118505380540
Explicación: La concatenación da como resultado «1101110010111011110001001101010111100». El valor decimal equivalente es 118505380540.

Entrada: N = 3
Salida: 27
Explicación: En binario, 1, 2 y 3 corresponden a “1”, “10” y “11”. Su concatenación da como resultado “11011”, que corresponde al valor decimal de 27.

Enfoque: la idea es iterar sobre el rango [1, N] . Para cada i ^-ésimo número, concatene la representación binaria del número i usando la propiedad Bitwise XOR . Siga los pasos a continuación para resolver el problema:

1. Inicialice dos variables, l y ans con 0 , donde l almacena la posición actual del bit en la string binaria final de cualquier i ^-ésimo número y ans almacenará la respuesta final.
2. Iterar de i = 1 a N + 1 .
3. Si (i & (i – 1)) es igual a 0 , simplemente incremente el valor de l en 1 , donde & es el operador AND bit a bit .
4. Después de eso, el desplazamiento a la izquierda responde con l y luego O bit a bit el resultado con i .
5. Después y atravesando, imprima ans como la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the decimal value by
// concatenating the numbers from 1 to N
int concatenatedBinary(int n)
{
 
    // Stores count of
    // bits in a number
    int l = 0;
 
    // Stores decimal value by
    // concatenating 1 to N
    int ans = 0;
 
    // Iterate over the range [1, n]
    for (int i = 1; i < n + 1; i++){
 
        // If i is a power of 2
        if ((i & (i - 1)) == 0)
              l += 1;
 
        // Update ans
        ans = ((ans << l) | i);
    }
 
    // Return ans
    return ans;
}
 
// Driver Code
int main()
{
    int n = 3;
 
    // Function Call
    cout << (concatenatedBinary(n));
 
  return 0;
}
 
// This code is contributed by mohiy kumar 29

// Java program for the above approach
class GFG
{
     
    // Function to find the decimal value by
    // concatenating the numbers from 1 to N
    static int concatenatedBinary(int n)
    {
     
        // Stores count of
        // bits in a number
        int l = 0;
     
        // Stores decimal value by
        // concatenating 1 to N
        int ans = 0;
     
        // Iterate over the range [1, n]
        for (int i = 1; i < n + 1; i++){
     
            // If i is a power of 2
            if ((i & (i - 1)) == 0)
                  l += 1;
     
            // Update ans
            ans = ((ans << l) | i);
        }
     
        // Return ans
        return ans;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int n = 3;
     
        // Function Call
        System.out.println(concatenatedBinary(n));
    }
}
 
// This code is contributed by AnkThon

# Python program for the above approach
 
# Function to find the decimal value by
# concatenating the numbers from 1 to N
def concatenatedBinary(n):
 
    # Stores count of
    # bits in a number
    l = 0
 
    # Stores decimal value by
    # concatenating 1 to N
    ans = 0
 
    # Iterate over the range [1, n]
    for i in range(1, n + 1):
 
        # If i is a power of 2
        if i & (i - 1) == 0:
 
            # Update l
            l += 1
 
        # Update ans
        ans = ((ans << l) | i)
 
    # Return ans
    return(ans)
 
# Driver Code
if __name__ == '__main__':
    n = 3
 
    # Function Call
    print(concatenatedBinary(n))

// C# program to implement
// the above approach 
using System;
class GFG
{
     
    // Function to find the decimal value by
    // concatenating the numbers from 1 to N
    static int concatenatedBinary(int n)
    {
     
        // Stores count of
        // bits in a number
        int l = 0;
     
        // Stores decimal value by
        // concatenating 1 to N
        int ans = 0;
     
        // Iterate over the range [1, n]
        for (int i = 1; i < n + 1; i++)
        {
     
            // If i is a power of 2
            if ((i & (i - 1)) == 0)
                  l += 1;
     
            // Update ans
            ans = ((ans << l) | i);
        }
     
        // Return ans
        return ans;
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 3;
     
        // Function Call
        Console.WriteLine(concatenatedBinary(n));
    }
}
 
// This code is contributed by sanjoy_62

<script>
//Javascript program to implement
// the above approach
 
// Function to find the decimal value by
// concatenating the numbers from 1 to N
function concatenatedBinary(n)
{
 
    // Stores count of
    // bits in a number
    var l = 0;
 
    // Stores decimal value by
    // concatenating 1 to N
    var ans = 0;
 
    // Iterate over the range [1, n]
    for (var i = 1; i < n + 1; i++){
 
        // If i is a power of 2
        if ((i & (i - 1)) == 0)
              l += 1;
 
        // Update ans
        ans = parseInt((ans << l) | i);
    }
 
    // Return ans
    return ans;
}
 
 
var n = 3;
// Function Call
document.write(concatenatedBinary(n));
 
//This code is contributed by SoumikMondal
</script>

27

Complejidad temporal: O(N)
Espacio auxiliar: O(1)