Dado un entero positivo N , la tarea es calcular la suma de todos los decimales que se pueden expresar como representaciones binarias de los primeros N números naturales .
Ejemplos:
Entrada: N = 3
Salida: 22
Explicación:
La representación binaria de 1 es 01.
La representación binaria de 2 es 10.
La representación binaria de 3 es 11.
Por lo tanto, la suma requerida = 01 + 10 + 11 = 22.Entrada: N = 5
Salida: 223
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar un ciclo sobre el rango [1, N] y en cada iteración convertir el número actual a su representación binaria y agregarlo a la suma total . Después de sumar todos los números, imprime la suma como resultado.
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(32)
Enfoque eficiente: el enfoque anterior también se puede optimizar al encontrar la contribución de los números que no tienen la misma posición de bit más significativo (MSB) que N y luego encontrar la contribución del MSB del resto de los números. Siga los pasos para resolver el problema:
- Inicialice una variable, digamos ans como 0 para almacenar la suma de todos los números en la representación binaria de los primeros N números naturales.
- Iterar hasta que el valor de N sea al menos 0 y realizar los siguientes pasos:
- Almacene la posición MSB del número N en una variable X y almacene el valor de 2 (X – 1) en una variable, digamos A.
- Inicialice una variable, diga cur como 0 para almacenar la contribución de los números que no tienen la misma posición de MSB que N .
- Itere sobre el rango [1, X] y, en cada iteración, agregue A a la variable cur y luego multiplique A por 10 .
- Después de los pasos anteriores, agregue el valor de cur a ans y almacene los elementos restantes en la variable rem como (N – 2 X + 1) .
- Sume la contribución por parte del MSB del resto de los números sumando (rem * 10 X ) al ans .
- Actualice el valor de N a (rem – 1) para la próxima iteración.
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
// Function to find the sum of first
// N natural numbers represented
// in binary representation
void sumOfBinaryNumbers(int n)
{
// Stores the resultant sum
int ans = 0;
int one = 1;
// Iterate until the value of
// N is greater than 0
while (1) {
// If N is less than 2
if (n <= 1) {
ans = (ans + n) % MOD;
break;
}
// Store the MSB position of N
int x = log2(n);
int cur = 0;
int add = (one << (x - 1));
// Iterate in the range [1, x]
// and add the contribution of
// the numbers from 1 to (2^x-1)
for (int i = 1; i <= x; i++) {
// Update the value of the
// cur and add
cur = (cur + add) % MOD;
add = (add * 10 % MOD);
}
// Add the cur to ans
ans = (ans + cur) % MOD;
// Store the remaining numbers
int rem = n - (one << x) + 1;
// Add the contribution by MSB
// by the remaining numbers
int p = pow(10, x);
p = (p * (rem % MOD)) % MOD;
ans = (ans + p) % MOD;
// The next iteration will
// be repeated for 2^x - 1
n = rem - 1;
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
int N = 3;
sumOfBinaryNumbers(N);
return 0;
}
Java
/// Java program for the above approach
import java.io.*;
import java.lang.*;
class GFG
{
static final int MOD = 1000000007;
// Function to find the sum of first
// N natural numbers represented
// in binary representation
static void sumOfBinaryNumbers(int n)
{
// Stores the resultant sum
int ans = 0;
int one = 1;
// Iterate until the value of
// N is greater than 0
while (true) {
// If N is less than 2
if (n <= 1) {
ans = (ans + n) % MOD;
break;
}
// Store the MSB position of N
int x = (int)(Math.log(n) / Math.log(2));
int cur = 0;
int add = (int)(Math.pow(2, (x - 1)));
// Iterate in the range [1, x]
// and add the contribution of
// the numbers from 1 to (2^x-1)
for (int i = 1; i <= x; i++) {
// Update the value of the
// cur and add
cur = (cur + add) % MOD;
add = (add * 10 % MOD);
}
// Add the cur to ans
ans = (ans + cur) % MOD;
// Store the remaining numbers
int rem = n - (int)(Math.pow(2, x)) + 1;
// Add the contribution by MSB
// by the remaining numbers
int p = (int)Math.pow(10, x);
p = (p * (rem % MOD)) % MOD;
ans = (ans + p) % MOD;
// The next iteration will
// be repeated for 2^x - 1
n = rem - 1;
}
// Print the result
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
sumOfBinaryNumbers(N);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program for the above approach from math import log2, pow MOD = 1000000007 # Function to find the sum of first # N natural numbers represented # in binary representation def sumOfBinaryNumbers(n): # Stores the resultant sum ans = 0 one = 1 # Iterate until the value of # N is greater than 0 while (1): # If N is less than 2 if (n <= 1): ans = (ans + n) % MOD break # Store the MSB position of N x = int(log2(n)) cur = 0 add = (one << (x - 1)) # Iterate in the range [1, x] # and add the contribution of # the numbers from 1 to (2^x-1) for i in range(1, x + 1, 1): # Update the value of the # cur and add cur = (cur + add) % MOD add = (add * 10 % MOD) # Add the cur to ans ans = (ans + cur) % MOD # Store the remaining numbers rem = n - (one << x) + 1 # Add the contribution by MSB # by the remaining numbers p = pow(10, x) p = (p * (rem % MOD)) % MOD ans = (ans + p) % MOD # The next iteration will # be repeated for 2^x - 1 n = rem - 1 # Print the result print(int(ans)) # Driver Code if __name__ == '__main__': N = 3 sumOfBinaryNumbers(N) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
const int MOD = 1000000007;
// Function to find the sum of first
// N natural numbers represented
// in binary representation
static void sumOfBinaryNumbers(int n)
{
// Stores the resultant sum
int ans = 0;
int one = 1;
// Iterate until the value of
// N is greater than 0
while (true)
{
// If N is less than 2
if (n <= 1)
{
ans = (ans + n) % MOD;
break;
}
// Store the MSB position of N
int x = (int)Math.Log(n, 2);
int cur = 0;
int add = (one << (x - 1));
// Iterate in the range [1, x]
// and add the contribution of
// the numbers from 1 to (2^x-1)
for(int i = 1; i <= x; i++)
{
// Update the value of the
// cur and add
cur = (cur + add) % MOD;
add = (add * 10 % MOD);
}
// Add the cur to ans
ans = (ans + cur) % MOD;
// Store the remaining numbers
int rem = n - (one << x) + 1;
// Add the contribution by MSB
// by the remaining numbers
int p = (int)Math.Pow(10, x);
p = (p * (rem % MOD)) % MOD;
ans = (ans + p) % MOD;
// The next iteration will
// be repeated for 2^x - 1
n = rem - 1;
}
// Print the result
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
int N = 3;
sumOfBinaryNumbers(N);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program to implement
// the above approach
let MOD = 1000000007;
// Function to find the sum of first
// N natural numbers represented
// in binary representation
function sumOfBinaryNumbers(n)
{
// Stores the resultant sum
let ans = 0;
let one = 1;
// Iterate until the value of
// N is greater than 0
while (true) {
// If N is less than 2
if (n <= 1) {
ans = (ans + n) % MOD;
break;
}
// Store the MSB position of N
let x = Math.floor(Math.log(n) / Math.log(2));
let cur = 0;
let add = Math.floor(Math.pow(2, (x - 1)));
// Iterate in the range [1, x]
// and add the contribution of
// the numbers from 1 to (2^x-1)
for (let i = 1; i <= x; i++) {
// Update the value of the
// cur and add
cur = (cur + add) % MOD;
add = (add * 10 % MOD);
}
// Add the cur to ans
ans = (ans + cur) % MOD;
// Store the remaining numbers
let rem = n - Math.floor(Math.pow(2, x)) + 1;
// Add the contribution by MSB
// by the remaining numbers
let p = Math.floor(Math.pow(10, x));
p = (p * (rem % MOD)) % MOD;
ans = (ans + p) % MOD;
// The next iteration will
// be repeated for 2^x - 1
n = rem - 1;
}
// Print the result
document.write(ans);
}
// Driver code
let N = 3;
sumOfBinaryNumbers(N);
</script>
Producción:
22
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por karangargabc y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA