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 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
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 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> |
Time Complexity: O(log2N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!