Dado un entero positivo N , la tarea es encontrar la suma de todas las diferencias de bits consecutivas de 0 a N.
Nota: si la longitud de bits es diferente para dos números como (3, 4), agregue 0 al principio (011, 100).
Ejemplos:
Entrada: N = 3
Salida: 4
Explicación:
Diferencias de bits de (0, 1) + (1, 2) + (2, 3) = 1 + 2 + 1 = 4.
Entrada: N = 7
Salida: 11
Enfoque ingenuo:
el enfoque más simple es comparar los dos valores consecutivos dentro del rango bit a bit y averiguar en cuántos bits difieren ambos números. Agregue esta diferencia de bits a la suma. La suma final así obtenida es la solución requerida.
Complejidad de tiempo:
Enfoque O(N)
: Se deben realizar las siguientes observaciones para optimizar la solución anterior:
- Las diferencias de bits consecutivas de los números siguen un patrón, es decir, cada valor X que es igual a (2 i ) tiene una diferencia de bits de (i + 1) con su número anterior y los números (2 i – 1) por encima de X y (2 i ). – 1) los números debajo de X siguen el mismo patrón.
- Para X = 4 (2 2 ), i = 2 tiene una diferencia de bits (2 + 1) y los números (1, 2, 3) y (5, 6, 7) siguen el mismo patrón de diferencia de bits.
For X = 4, the pattern is as follows: NUM BIT Diff 1 1(0, 1) 2 2(1, 2) 3 1(2, 3) 4 3(3, 4) 5 1(4, 5) 6 2(5, 6) 7 1(6, 7)
Siga los pasos a continuación para resolver el problema:
- Para cada N , encuentre el número más cercano menor o igual a N, que es una potencia de 2. Digamos que ese número es M .
- Para todos los números menores que M, se puede usar el siguiente enfoque recursivo para encontrar la suma de las diferencias de bits consecutivas.
Count(i) = (i + 1) + 2 * Count(i – 1)
donde i es el exponente de la potencia de 2 más cercana.
- Inicialice una array de tamaño 65 (indexación basada en 0) para almacenar los valores obtenidos al usar la función recursiva Count(), de modo que en el futuro, si se necesitan los mismos valores de Count(), se pueden obtener directamente sin llamar recursivamente la función Count() para ahorrar tiempo.
- Repita el mismo proceso para los números restantes que son mayores que M usando la siguiente fórmula.
Suma = Suma + (i+1) + Cuenta(i-1)
Por ejemplo:
Para N = 10, calcule la suma de la potencia de 2 más cercana que es M = 8, usando Count(3) y luego repita el proceso para los números restantes mayores que 8.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
long long a[65] = { 0 };
// Recursive function to count
// the sum of bit differences
// of numbers from 1 to
// pow(2, (i+1)) - 1
long long Count(int i)
{
// base cases
if (i == 0)
return 1;
else if (i < 0)
return 0;
// Recursion call if the sum
// of bit difference of numbers
// around i are not calculated
if (a[i] == 0) {
a[i] = (i + 1) + 2 * Count(i - 1);
return a[i];
}
// return the sum of bit
// differences if already
// calculated
else
return a[i];
}
// Function to calculate the
// sum of bit differences up to N
long long solve(long long n)
{
long long i, sum = 0;
while (n > 0) {
// nearest smaller power
// of 2
i = log2(n);
// remaining numbers
n = n - pow(2, i);
// calculate the count
// of bit diff
sum = sum + (i + 1) + Count(i - 1);
}
return sum;
}
// Driver code
int main()
{
long long n = 7;
cout << solve(n) << endl;
return 0;
}
Java
// Java program for the above problem
import java.util.*;
class GFG{
static int a[] = new int[65];
// Recursive function to count
// the sum of bit differences
// of numbers from 1 to
// pow(2, (i+1)) - 1
static int Count(int i)
{
// base cases
if (i == 0)
return 1;
else if (i < 0)
return 0;
// Recursion call if the sum
// of bit difference of numbers
// around i are not calculated
if (a[i] == 0)
{
a[i] = (i + 1) + 2 * Count(i - 1);
return a[i];
}
// return the sum of bit
// differences if already
// calculated
else
return a[i];
}
// Function to calculate the
// sum of bit differences up to N
static int solve(int n)
{
int i, sum = 0;
while (n > 0)
{
// nearest smaller power
// of 2
i = (int)(Math.log(n) / Math.log(2));
// remaining numbers
n = n - (int)Math.pow(2, i);
// calculate the count
// of bit diff
sum = sum + (i + 1) + Count(i - 1);
}
return sum;
}
// Driver code
public static void main(String[] args)
{
int n = 7;
System.out.println(solve(n));
}
}
// This code is contributed by rock_cool
Python3
# Python3 program for the above problem import math a = [0] * 65 # Recursive function to count # the sum of bit differences # of numbers from 1 to # pow(2, (i+1)) - 1 def Count(i): # Base cases if (i == 0): return 1 elif (i < 0): return 0 # Recursion call if the sum # of bit difference of numbers # around i are not calculated if (a[i] == 0): a[i] = (i + 1) + 2 * Count(i - 1) return a[i] # Return the sum of bit # differences if already # calculated else: return a[i] # Function to calculate the # sum of bit differences up to N def solve(n): sum = 0 while (n > 0): # Nearest smaller power # of 2 i = int(math.log2(n)) # Remaining numbers n = n - pow(2, i) # Calculate the count # of bit diff sum = sum + (i + 1) + Count(i - 1) return sum # Driver code n = 7 print(solve(n)) # This code is contributed by sanjoy_62
C#
// C# program for the above problem
using System;
class GFG{
static int []a = new int[65];
// Recursive function to count
// the sum of bit differences
// of numbers from 1 to
// pow(2, (i+1)) - 1
static int Count(int i)
{
// base cases
if (i == 0)
return 1;
else if (i < 0)
return 0;
// Recursion call if the sum
// of bit difference of numbers
// around i are not calculated
if (a[i] == 0)
{
a[i] = (i + 1) + 2 * Count(i - 1);
return a[i];
}
// return the sum of bit
// differences if already
// calculated
else
return a[i];
}
// Function to calculate the
// sum of bit differences up to N
static int solve(int n)
{
int i, sum = 0;
while (n > 0)
{
// nearest smaller power
// of 2
i = (int)(Math.Log(n) / Math.Log(2));
// remaining numbers
n = n - (int)Math.Pow(2, i);
// calculate the count
// of bit diff
sum = sum + (i + 1) + Count(i - 1);
}
return sum;
}
// Driver code
public static void Main(String[] args)
{
int n = 7;
Console.Write(solve(n));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program for the above problem
let a = new Array(65);
a.fill(0);
// Recursive function to count
// the sum of bit differences
// of numbers from 1 to
// pow(2, (i+1)) - 1
function Count(i)
{
// base cases
if (i == 0)
return 1;
else if (i < 0)
return 0;
// Recursion call if the sum
// of bit difference of numbers
// around i are not calculated
if (a[i] == 0) {
a[i] = (i + 1) + 2 * Count(i - 1);
return a[i];
}
// return the sum of bit
// differences if already
// calculated
else
return a[i];
}
// Function to calculate the
// sum of bit differences up to N
function solve(n)
{
let i, sum = 0;
while (n > 0) {
// nearest smaller power
// of 2
i = parseInt(Math.log(n) / Math.log(2), 10);
// remaining numbers
n = n - parseInt(Math.pow(2, i), 10);
// calculate the count
// of bit diff
sum = sum + (i + 1) + Count(i - 1);
}
return sum;
}
let n = 7;
document.write(solve(n));
</script>
Producción:
11
Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(1)