Dado un número N , la tarea es calcular el número total de bits diferentes correspondientes en la representación binaria para cada número consecutivo de 0 a N.
Ejemplos:
Entrada: N = 5
Salida: 8
Explicación:
Representación binaria de números son:
0 -> 000,
1 -> 001,
2 -> 010,
3 -> 011,
4 -> 100,
5 -> 101
Entre 1 y 0 – > 1 bit es diferente
Entre 2 y 1 -> 2 bits son diferentes
Entre 3 y 2 -> 1 bit es diferente
Entre 4 y 3 -> 3 bits son diferentes
Entre 5 y 4 -> 1 bit es diferente
Total = 1 + 2 + 1 + 3 + 1 = 8
Entrada: N = 11
Salida: 19
Enfoque ingenuo: la idea es iterar de 0 a N y, para cada par de elementos consecutivos, encontrar la cantidad de bits diferentes para cada par de elementos utilizando el enfoque que se analiza en este artículo.
Complejidad de Tiempo: O(N*log N)
Espacio Auxiliar: (1)
Enfoque Eficiente: Para el enfoque eficiente tenemos que observar lo siguiente:
number: 1 2 3 4 5 6 7 8 bit_diff: 1 2 1 3 1 2 1 4 sum_diff: 1 3 4 7 8 10 11 15
De los cálculos anteriores podemos observar lo siguiente:
- Si N es una potencia perfecta de 2, entonces la suma total de los diferentes bits correspondientes de 0 a N viene dada por:
suma_diferencia = (2 x+1 -1)
donde x = log2(N)
- Si N no es una potencia perfecta de 2, entonces se puede representar como la suma de la potencia perfecta de 2 como:
norte = 2 un + 2 segundo + … + 2 x
- Por lo tanto, la suma total de los diferentes bits correspondientes de 0 a N se puede calcular como:
sum_diff = (2 a+1 -1) + (2 b+1 -1) + … + (2 x+1 -1).
Por ejemplo:
Si N = 8, entonces
La representación binaria de 8 es “1000”
Por lo tanto, 11 = 2 3
cuenta total = (2 3+1 – 1)
cuenta total = 8 – 1 = 7.
Si N = 11, entonces
La representación binaria de 11 es “1011”
Por lo tanto, 11 = 2 3 + 2 1 + 2 0
=> recuento total = (2 3+1 – 1) + (2 1+1 – 1) + (2 0+1 – 1)
=> total cuenta = 15 + 3 + 1 = 19.
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;
// Function to implement fast
// exponentiation
int binpow(int a, int b)
{
int res = 1;
while (b) {
if (b & 1)
res = res * a;
a = a * a;
b /= 2;
}
return res;
}
// Function to return the value
// for powers of 2
int find(int x)
{
if (x == 0)
return 0;
int p = log2(x);
return binpow(2, p + 1) - 1;
}
// Function to convert N into binary
string getBinary(int n)
{
// To store binary representation
string ans = "";
// Iterate each digit of n
while (n) {
int dig = n % 2;
ans += to_string(dig);
n /= 2;
}
// Return binary representation
return ans;
}
// Function to find difference in bits
int totalCountDifference(int n)
{
// Get binary representation
string ans = getBinary(n);
// total number of bit
// differences from 0 to N
int req = 0;
// Iterate over each binary bit
for (int i = 0; i < ans.size(); i++) {
// If current bit is '1' then add
// the count of current bit
if (ans[i] == '1') {
req += find(binpow(2, i));
}
}
return req;
}
// Driver Code
int main()
{
// Given Number
int N = 5;
// Function Call
cout << totalCountDifference(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.Math;
class GFG{
// Function to implement fast
// exponentiation
static int binpow(int a, int b)
{
int res = 1;
while (b > 0)
{
if (b % 2 == 1)
res = res * a;
a = a * a;
b /= 2;
}
return res;
}
// Function to return the
// value for powers of 2
static int find(int x)
{
if (x == 0)
return 0;
int p = (int)(Math.log(x) / Math.log(2));
return binpow(2, p + 1) - 1;
}
// Function to convert N into binary
static String getBinary(int n)
{
// To store the binary representation
String ans = "";
// Iterate each digit of n
while (n > 0)
{
int dig = n % 2;
ans += dig;
n /= 2;
}
// Return binary representation
return ans;
}
// Function to find difference in bits
static int totalCountDifference(int n)
{
// Get binary representation
String ans = getBinary(n);
// total number of bit
// differences from 0 to N
int req = 0;
// Iterate over each binary bit
for(int i = 0; i < ans.length(); i++)
{
// If current bit is '1' then add
// the count of current bit
if (ans.charAt(i) == '1')
{
req += find(binpow(2, i));
}
}
return req;
}
// Driver code
public static void main (String[] args)
{
// Given number
int n = 5;
System.out.print(totalCountDifference(n));
}
}
// This code is contributed by spp____
Python3
# Python3 program for the above approach from math import log # Function to implement fast # exponentiation def binpow(a, b): res = 1 while (b > 0): if (b % 2 == 1): res = res * a a = a * a b //= 2 return res # Function to return the value # for powers of 2 def find(x): if (x == 0): return 0 p = log(x) / log(2) return binpow(2, p + 1) - 1 # Function to convert N into binary def getBinary(n): # To store binary representation ans = "" # Iterate each digit of n while (n > 0): dig = n % 2 ans += str(dig) n //= 2 # Return binary representation return ans # Function to find difference in bits def totalCountDifference(n): # Get binary representation ans = getBinary(n) # total number of bit # differences from 0 to N req = 0 # Iterate over each binary bit for i in range(len(ans)): # If current bit is '1' then add # the count of current bit if (ans[i] == '1'): req += find(binpow(2, i)) return req # Driver Code # Given Number N = 5 # Function Call print(totalCountDifference(N)) # This code is contributed by shubhamsingh10
C#
// C# program for the above approach
using System;
class GFG{
// Function to implement fast
// exponentiation
static int binpow(int a, int b)
{
int res = 1;
while (b > 0)
{
if (b % 2 == 1)
res = res * a;
a = a * a;
b /= 2;
}
return res;
}
// Function to return the
// value for powers of 2
static int find(int x)
{
if (x == 0)
return 0;
int p = (int)(Math.Log(x) / Math.Log(2));
return binpow(2, p + 1) - 1;
}
// Function to convert N into binary
static String getBinary(int n)
{
// To store the binary representation
String ans = "";
// Iterate each digit of n
while (n > 0)
{
int dig = n % 2;
ans += dig;
n /= 2;
}
// Return binary representation
return ans;
}
// Function to find difference in bits
static int totalCountDifference(int n)
{
// Get binary representation
string ans = getBinary(n);
// total number of bit
// differences from 0 to N
int req = 0;
// Iterate over each binary bit
for(int i = 0; i < ans.Length; i++)
{
// If current bit is '1' then add
// the count of current bit
if (ans[i] == '1')
{
req += find(binpow(2, i));
}
}
return req;
}
// Driver code
public static void Main()
{
// Given number
int n = 5;
Console.Write(totalCountDifference(n));
}
}
// This code is contributed by Nidhi_biet
Javascript
<script>
// Javascript program for the above approach\
// Function to implement fast
// exponentiation
function binpow(a, b) {
let res = 1;
while (b) {
if (b & 1)
res = res * a;
a = a * a;
b = Math.floor(b / 2);
}
return res;
}
// Function to return the value
// for powers of 2
function find(x) {
if (x == 0)
return 0;
let p = Math.log2(x);
return binpow(2, p + 1) - 1;
}
// Function to convert N into binary
function getBinary(n) {
// To store binary representation
let ans = "";
// Iterate each digit of n
while (n) {
let dig = n % 2;
ans += String(dig);
n = Math.floor(n / 2);
}
// Return binary representation
return ans;
}
// Function to find difference in bits
function totalCountDifference(n)
{
// Get binary representation
let ans = getBinary(n);
// total number of bit
// differences from 0 to N
let req = 0;
// Iterate over each binary bit
for (let i = 0; i < ans.length; i++) {
// If current bit is '1' then add
// the count of current bit
if (ans[i] == '1') {
req += find(binpow(2, i));
}
}
return req;
}
// Driver Code
// Given Number
let N = 5;
// Function Call
document.write(totalCountDifference(N));
// This code is contributed by _saurabh_jaiswal
</script>
8
Complejidad de Tiempo: O((log N) 2 )
Espacio Auxiliar: (1)
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA