Given a number N, the task is to calculate the total number of corresponding different bit in the binary representation for every consecutive number from 0 to N.
Examples:
Input: N = 5
Output: 8
Explanation:
Binary Representation of numbers are:
0 -> 000,
1 -> 001,
2 -> 010,
3 -> 011,
4 -> 100,
5 -> 101
Between 1 and 0 -> 1 bit is different
Between 2 and 1 -> 2 bits are different
Between 3 and 2 -> 1 bit is different
Between 4 and 3 -> 3 bits are different
Between 5 and 4 -> 1 bit is different
Total = 1 + 2 + 1 + 3 + 1 = 8
Input: N = 11
Output: 19
For Naive and Efficient Approach please refer to the previous post of this article.
More Efficient Approach: To optimize the above methods, we can use Recursion. To solve the problem, the following observations need to be made
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
We can observe that for N = [1, 2, 3, 4, …..], the sum of different bits in consecutive elements forms the sequence [1, 3, 4, 7, 8, ……]. Hence, Nth term of this series will be our required answer, which can be calculated as:
a(n) = a(n / 2) + n; with base case as a(1) = 1
Below is the implementation for above Recursive approach:
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 Nint totalCountDifference(int n){ // Base case if (n == 1) return 1; // Calculate the Nth term return n + totalCountDifference(n / 2);}// Driver Codeint 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 recursionclass GFG{// Recursive function to find sum// of different bits between// consecutive numbers from 0 to Nstatic int totalCountDifference(int n){ // Base case if (n == 1) return 1; // Calculate the Nth term return n + totalCountDifference(n / 2);}// Driver Codepublic 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 Ndef totalCountDifference (n): # Base case if (n == 1): return 1 # Calculate the Nth term return n + totalCountDifference(n // 2)# Driver code# Given numberN = 5# Function callprint(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 recursionusing System;class GFG{// Recursive function to find sum// of different bits between// consecutive numbers from 0 to Nstatic int totalCountDifference(int n){ // Base case if (n == 1) return 1; // Calculate the Nth term return n + totalCountDifference(n / 2);}// Driver Codepublic 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 Nfunction 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> |
Output:
8
Time Complexity: O(log2N)
Auxiliary Space: O(1)
Most Efficient Approach: Dynamic Programming (Using Memoization)
The above recursive approach can give MLE (Memory Limit Exceeded) for larger inputs due to recursive calls which will use stack spaces.
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 Nint 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 Codeint 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 Programmingimport 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 Programmingdp = [-1] * 101# Recursive function to find sum# of different bits between# consecutive numbers from 0 to Ndef 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 NumberN = 5# Function Callprint(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 Programmingusing System;class GFG{ static int []dp = new int[101];// Recursive function to find sum// of different bits between// consecutive numbers from 0 to Nstatic 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 Codepublic 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 memoizationlet dp = new Array(1001);dp.fill(-1);// Recursive function to find sum// of different bits between// consecutive numbers from 0 to Nfunction 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 Numberlet N = 5// Function Calldocument.write(totalCountDifference(N))// This code is contributed by Samim Hossain Mondal.</script> |
Time Complexity: O(log2N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!