Given a positive integer N, the task is to calculate the sum of all decimals which can be expressed as binary representations of first N natural numbers.
Examples:
Input: N = 3
Output: 22
Explanation:
The Binary Representation of 1 is 01.
The Binary Representation of 2 is 10.
The Binary Representation of 3 is 11.
Therefore, required sum = 01 + 10 + 11 = 22.Input: N = 5
Output: 223
Naive Approach: The simplest approach to solve the problem is to iterate a loop over the range [1, N] and in each iteration convert the current number to its binary representation and add it to the overall sum. After adding all the numbers, print the sum as the result.
Time Complexity: O(N * log(N))
Auxiliary Space: O(32)
Efficient Approach: The above approach can also be optimized by finding the contribution of numbers not having the same most significant bit (MSB) position as N and then find the contribution by the MSB of the rest of the numbers. Follow the steps to solve the problem:
- Initialize a variable, say ans as 0 to store the sum of all the numbers in the binary representation of first N natural numbers.
- Iterate until the value of N is at least 0, and perform the following steps:
- Store the MSB position of the number N in a variable X and store the value of 2(X – 1) in a variable, say A.
- Initialize a variable, say cur as 0 to store the contribution of numbers not having the same MSB position as N.
- Iterate over the range [1, X], and in each iteration, add A to the variable cur and then multiply A by 10.
- After the above steps, add the value of cur to ans and store the remaining elements in variable rem as (N – 2X + 1).
- Add the contribution by the MSB of the rest of the numbers by adding (rem * 10X) to the ans.
- Update the value of N to (rem – 1) for the next iteration.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;const int MOD = 1e9 + 7;// Function to find the sum of first// N natural numbers represented// in binary representationvoid sumOfBinaryNumbers(int n){ // Stores the resultant sum int ans = 0; int one = 1; // Iterate until the value of // N is greater than 0 while (1) { // If N is less than 2 if (n <= 1) { ans = (ans + n) % MOD; break; } // Store the MSB position of N int x = log2(n); int cur = 0; int add = (one << (x - 1)); // Iterate in the range [1, x] // and add the contribution of // the numbers from 1 to (2^x-1) for (int i = 1; i <= x; i++) { // Update the value of the // cur and add cur = (cur + add) % MOD; add = (add * 10 % MOD); } // Add the cur to ans ans = (ans + cur) % MOD; // Store the remaining numbers int rem = n - (one << x) + 1; // Add the contribution by MSB // by the remaining numbers int p = pow(10, x); p = (p * (rem % MOD)) % MOD; ans = (ans + p) % MOD; // The next iteration will // be repeated for 2^x - 1 n = rem - 1; } // Print the result cout << ans;}// Driver Codeint main(){ int N = 3; sumOfBinaryNumbers(N); return 0;} |
Java
/// Java program for the above approachimport java.io.*;import java.lang.*;class GFG{ static final int MOD = 1000000007; // Function to find the sum of first // N natural numbers represented // in binary representation static void sumOfBinaryNumbers(int n) { // Stores the resultant sum int ans = 0; int one = 1; // Iterate until the value of // N is greater than 0 while (true) { // If N is less than 2 if (n <= 1) { ans = (ans + n) % MOD; break; } // Store the MSB position of N int x = (int)(Math.log(n) / Math.log(2)); int cur = 0; int add = (int)(Math.pow(2, (x - 1))); // Iterate in the range [1, x] // and add the contribution of // the numbers from 1 to (2^x-1) for (int i = 1; i <= x; i++) { // Update the value of the // cur and add cur = (cur + add) % MOD; add = (add * 10 % MOD); } // Add the cur to ans ans = (ans + cur) % MOD; // Store the remaining numbers int rem = n - (int)(Math.pow(2, x)) + 1; // Add the contribution by MSB // by the remaining numbers int p = (int)Math.pow(10, x); p = (p * (rem % MOD)) % MOD; ans = (ans + p) % MOD; // The next iteration will // be repeated for 2^x - 1 n = rem - 1; } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { int N = 3; sumOfBinaryNumbers(N); }}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approachfrom math import log2, powMOD = 1000000007# Function to find the sum of first# N natural numbers represented# in binary representationdef sumOfBinaryNumbers(n): # Stores the resultant sum ans = 0 one = 1 # Iterate until the value of # N is greater than 0 while (1): # If N is less than 2 if (n <= 1): ans = (ans + n) % MOD break # Store the MSB position of N x = int(log2(n)) cur = 0 add = (one << (x - 1)) # Iterate in the range [1, x] # and add the contribution of # the numbers from 1 to (2^x-1) for i in range(1, x + 1, 1): # Update the value of the # cur and add cur = (cur + add) % MOD add = (add * 10 % MOD) # Add the cur to ans ans = (ans + cur) % MOD # Store the remaining numbers rem = n - (one << x) + 1 # Add the contribution by MSB # by the remaining numbers p = pow(10, x) p = (p * (rem % MOD)) % MOD ans = (ans + p) % MOD # The next iteration will # be repeated for 2^x - 1 n = rem - 1 # Print the result print(int(ans))# Driver Codeif __name__ == '__main__': N = 3 sumOfBinaryNumbers(N)# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;class GFG{ const int MOD = 1000000007;// Function to find the sum of first// N natural numbers represented// in binary representationstatic void sumOfBinaryNumbers(int n){ // Stores the resultant sum int ans = 0; int one = 1; // Iterate until the value of // N is greater than 0 while (true) { // If N is less than 2 if (n <= 1) { ans = (ans + n) % MOD; break; } // Store the MSB position of N int x = (int)Math.Log(n, 2); int cur = 0; int add = (one << (x - 1)); // Iterate in the range [1, x] // and add the contribution of // the numbers from 1 to (2^x-1) for(int i = 1; i <= x; i++) { // Update the value of the // cur and add cur = (cur + add) % MOD; add = (add * 10 % MOD); } // Add the cur to ans ans = (ans + cur) % MOD; // Store the remaining numbers int rem = n - (one << x) + 1; // Add the contribution by MSB // by the remaining numbers int p = (int)Math.Pow(10, x); p = (p * (rem % MOD)) % MOD; ans = (ans + p) % MOD; // The next iteration will // be repeated for 2^x - 1 n = rem - 1; } // Print the result Console.WriteLine(ans);}// Driver Codepublic static void Main(){ int N = 3; sumOfBinaryNumbers(N);}}// This code is contributed by ukasp |
Javascript
<script>// JavaScript program to implement// the above approachlet MOD = 1000000007; // Function to find the sum of first // N natural numbers represented // in binary representation function sumOfBinaryNumbers(n) { // Stores the resultant sum let ans = 0; let one = 1; // Iterate until the value of // N is greater than 0 while (true) { // If N is less than 2 if (n <= 1) { ans = (ans + n) % MOD; break; } // Store the MSB position of N let x = Math.floor(Math.log(n) / Math.log(2)); let cur = 0; let add = Math.floor(Math.pow(2, (x - 1))); // Iterate in the range [1, x] // and add the contribution of // the numbers from 1 to (2^x-1) for (let i = 1; i <= x; i++) { // Update the value of the // cur and add cur = (cur + add) % MOD; add = (add * 10 % MOD); } // Add the cur to ans ans = (ans + cur) % MOD; // Store the remaining numbers let rem = n - Math.floor(Math.pow(2, x)) + 1; // Add the contribution by MSB // by the remaining numbers let p = Math.floor(Math.pow(10, x)); p = (p * (rem % MOD)) % MOD; ans = (ans + p) % MOD; // The next iteration will // be repeated for 2^x - 1 n = rem - 1; } // Print the result document.write(ans); }// Driver code let N = 3; sumOfBinaryNumbers(N); </script> |
Output:
22
Time Complexity: O(log N)
Auxiliary Space: O(1)
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!
