Given an integer N, the task is to find the total number of bits toggled to obtain all numbers from 0 to N sequentially.
Examples:
Input: N = 5
Output: 8
Explanation:
Let’s represent numbers from 0 to 5 in binary:
000 -> 001 : 1 bit toggled
001 -> 010 : 2 bits toggled
010 -> 011 : 1 bit toggled
011 -> 100 : 3 bits toggled
100 -> 101 : 1 bit toggled
Hence, 8 bits toggledInput: N = 1
Output: 1
Approach:
Follow the steps below to solve the problems:
- The following observations need to be made to solve the problem:
The rightmost bit toggles every time.
(000) -> (001) -> (010) -> (011)
So, the contribution of this bit to the count will be N.
The next bit toggles after every 2 numbers.
(000) -> (001) -> (010) -> (011) -> (100)
Hence, the contribution of this bit to the count will be N/2.
- Thus, we can conclude that the i th least significant bit will contribute N/(2 i) to the count of toggles.
- Hence, the sum of N/(2i) where i is in the range [0, log2N], gives the required answer.
- Hence, initialize a variable ans. Add N to ans and update N to N/2. Repeat this process until N becomes 0, to get the final result.
Below is the implementation of the above approach:
C++
// C++ program to count // the number of toggles // required to generate // all numbers from 0 to N #include <bits/stdc++.h> using namespace std; typedef long long int ll; // Function to count and print // the required number of // toggles void solve(ll N) { // Store the count // of toggles ll ans = 0; while (N != 0) { // Add the contribution // of the current LSB ans += N; // Update N N /= 2; } // Print the result cout << ans << endl; } // Driver code int main() { ll N = 5; solve(N); return 0; } |
Java
// Java program to count the // number of toggles required // to generate all numbers // from 0 to N class GFG{ // Function to count and print // the required number of // toggles static void solve(int N) { // Store the count // of toggles int ans = 0; while (N != 0) { // Add the contribution // of the current LSB ans += N; // Update N N /= 2; } // Print the result System.out.println(ans); } // Driver code public static void main(String []args) { int N = 5; solve(N); } } // This code is contributed by Ritik Bansal |
Python3
# Python3 program to count # the number of toggles # required to generate # all numbers from 0 to N # Function to count and pr # the required number of # toggles def solve(N): # Store the count # of toggles ans = 0 while (N != 0): # Add the contribution # of the current LSB ans += N # Update N N //= 2 # Print the result print(ans) # Driver code N = 5solve(N) # This code is contributed by code_hunt |
C#
// C# program to count the // number of toggles required// to generate all numbers // from 0 to Nusing System;class GFG{// Function to count and print// the required number of// togglesstatic void solve(int N){ // Store the count // of toggles int ans = 0; while (N != 0) { // Add the contribution // of the current LSB ans += N; // Update N N /= 2; } // Print the result Console.Write(ans);}// Driver codepublic static void Main(string []args){ int N = 5; solve(N);}}// This code is contributed by rock_cool |
Javascript
<script>// Javascript program to count the // number of toggles required to // generate all numbers from 0 to N // Function to count and print // the required number of // toggles function solve(N) { // Store the count // of toggles let ans = 0; while (N != 0) { // Add the contribution // of the current LSB ans += N; // Update N N = parseInt(N / 2, 10); } // Print the result document.write(ans); } // Driver code let N = 5; solve(N); // This code is contributed by divyeshrabadiya07</script> |
Output:
8
Time Complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
