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
Para un enfoque ingenuo y eficiente, consulte la publicación anterior de este artículo.
Enfoque más eficiente: para optimizar los métodos anteriores, podemos usar Recursion . Para resolver el problema es necesario hacer las siguientes observaciones
Number: 0 1 2 3 4 5 6 7 Difference: 1 2 1 3 1 2 1 4 Sum: 1 3 4 7 8 10 11 15
Podemos observar que para N = [1, 2, 3, 4, …..] , la suma de diferentes bits en elementos consecutivos forma la secuencia [1, 3, 4, 7, 8, ……] . Por lo tanto, el término N de esta serie será nuestra respuesta requerida, que se puede calcular como:
un(n) = un(n / 2) + n; con el caso base como a(1) = 1
A continuación se muestra la implementación del enfoque recursivo anterior:
C++
// C++ program to find the sum
// of bit differences between
// consecutive numbers
// from 0 to N using recursion
#include <bits/stdc++.h>
using namespace std;
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
int totalCountDifference(int n)
{
// Base case
if (n == 1)
return 1;
// Calculate the Nth term
return n
+ totalCountDifference(n / 2);
}
// Driver Code
int main()
{
// Given Number
int N = 5;
// Function Call
cout << totalCountDifference(N);
return 0;
}
Java
// Java program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using recursion
class GFG{
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
static int totalCountDifference(int n)
{
// Base case
if (n == 1)
return 1;
// Calculate the Nth term
return n + totalCountDifference(n / 2);
}
// Driver Code
public static void main(String[] args)
{
// Given number
int N = 5;
// Function call
System.out.println(totalCountDifference(N));
}
}
// This code is contributed by himanshu77
Python3
# Python3 program to find the sum # of bit differences between # consecutive numbers from # 0 to N using recursion # Recursive function to find sum # of different bits between # consecutive numbers from 0 to N def totalCountDifference (n): # Base case if (n == 1): return 1 # Calculate the Nth term return n + totalCountDifference(n // 2) # Driver code # Given number N = 5 # Function call print(totalCountDifference(N)) # This code is contributed by himanshu77
C#
// C# program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using recursion
using System;
class GFG{
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
static int totalCountDifference(int n)
{
// Base case
if (n == 1)
return 1;
// Calculate the Nth term
return n + totalCountDifference(n / 2);
}
// Driver Code
public static void Main()
{
// Given number
int N = 5;
// Function call
Console.WriteLine(totalCountDifference(N));
}
}
// This code is contributed by himanshu77
Javascript
<script>
// JavaScript program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using recursion
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
function totalCountDifference(n)
{
// Base case
if (n == 1)
return 1;
// Calculate the Nth term
return n + totalCountDifference(Math.floor(n / 2));
}
// Driver Code
// Given number
let N = 5;
// Function call
document.write(totalCountDifference(N));
</script>
8
Complejidad de tiempo: O(log 2 N)
Espacio auxiliar: O(1)
Enfoque más eficiente: programación dinámica ( usando la memorización )
El enfoque recursivo anterior puede dar MLE (límite de memoria excedido) para entradas más grandes debido a llamadas recursivas que usarán espacios de pila.
C++
// C++ program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using Dynamic Programming
#include <bits/stdc++.h>
using namespace std;
static int dp[101];
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
int totalCountDifference(int n)
{
// Base case
if (n == 1)
return 1;
if (dp[n] != -1)
return dp[n];
// Calculate the Nth term
dp[n] = n + totalCountDifference(n / 2);
// Return dp
return dp[n];
}
// Driver Code
int main()
{
// Given Number
int N = 5;
memset(dp, -1, sizeof(dp));
// Function Call
cout << totalCountDifference(N);
return 0;
}
Java
// Java program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using Dynamic Programming
import java.util.*;
public class GFG
{
static int []dp = new int[101];
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
static int totalCountDifference(int n)
{
// Base case
if (n == 1)
return 1;
if (dp[n] != -1)
return dp[n];
// Calculate the Nth term
dp[n] = n + totalCountDifference(n / 2);
// Return dp
return dp[n];
}
// Driver Code
public static void main(String args[])
{
// Given Number
int N = 5;
for(int i = 0; i < 101; i++) {
dp[i] = -1;
}
// Function Call
System.out.print(totalCountDifference(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python
# Python program to find the sum # of bit differences between # consecutive numbers from # 0 to N using Dynamic Programming dp = [-1] * 101 # Recursive function to find sum # of different bits between # consecutive numbers from 0 to N def totalCountDifference(n): # Base case if (n == 1): return 1 if (dp[n] != -1): return dp[n] # Calculate the Nth term dp[n] = n + totalCountDifference(n // 2) # Return dp return dp[n] # Driver Code # Given Number N = 5 # Function Call print(totalCountDifference(N)) # This code is contributed by Samim Hossain Mondal.
C#
// C# program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using Dynamic Programming
using System;
class GFG
{
static int []dp = new int[101];
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
static int totalCountDifference(int n)
{
// Base case
if (n == 1)
return 1;
if (dp[n] != -1)
return dp[n];
// Calculate the Nth term
dp[n] = n + totalCountDifference(n / 2);
// Return dp
return dp[n];
}
// Driver Code
public static void Main()
{
// Given Number
int N = 5;
for(int i = 0; i < 101; i++) {
dp[i] = -1;
}
// Function Call
Console.Write(totalCountDifference(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program to find the sum
// of bit differences between
// consecutive numbers from
// 0 to N using Dynamic Programming
// Create an array for memoization
let dp = new Array(1001);
dp.fill(-1);
// Recursive function to find sum
// of different bits between
// consecutive numbers from 0 to N
function totalCountDifference(n) {
// Base case
if (n == 1) {
return 1;
}
if (dp[n] != -1) {
return dp[n];
}
// Calculate the Nth term
dp[n] = n + totalCountDifference(Math.floor(n / 2));
// Return dp
return dp[n];
}
// Driver Code
// Given Number
let N = 5
// Function Call
document.write(totalCountDifference(N))
// This code is contributed by Samim Hossain Mondal.
</script>
Complejidad de tiempo: O (log 2 N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por himanshu77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA