Sum of bit differences for numbers from 0 to N
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
Naive Approach: The idea is to iterate from 0 to N and for each pair of a consecutive elements, find the number of different bits for each pair of elements using the approach discussed in this article.
Time Complexity: O(N*log N)
Auxiliary Space: (1)
Efficient Approach: For the efficient approach we have to observe the following:
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
From the above calculations we can observe the following:
- If N is a perfect power of 2, then the total sum of corresponding different bits from 0 to N is given by:
sum_diff = (2x+1-1)
where x = log2(N)
- If N is not a perfect power of 2, then it can be represented as sum of perfect power of 2 as:
N = 2a + 2b + ā¦ + 2x
- Therefore the total sum of corresponding different bits from 0 to N can be calculated as:
sum_diff = (2a+1-1) + (2b+1-1) + ā¦ + (2x+1-1).
For Examples:
If N = 8, then
The binary representation of 8 is ā1000ā
Hence 11 = 23
total count = (23+1 ā 1)
total count = 8 ā 1 = 7.
If N = 11, then
The binary representation of 11 is ā1011ā
Hence 11 = 23 + 21 + 20
=> total count = (23+1 ā 1) + (21+1 ā 1) + (20+1 ā 1)
=> total count = 15 + 3 + 1 = 19.
Below is the implementation of the above approach:
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
Time Complexity: O((log N)2)
Auxiliary Space: (1)