Given an integer N, the task is to find the decimal value of the binary string formed by concatenating the binary representations of all numbers from 1 to N sequentially.
Examples:
Input: N = 12
Output: 118505380540
Explanation: The concatenation results in “1101110010111011110001001101010111100”. The equivalent decimal value is 118505380540.Input: N = 3
Output: 27
Explanation: In binary, 1, 2, and 3 correspond to “1”, “10”, and “11”. Their concatenation results in “11011”, which corresponds to the decimal value of 27.
Approach: The idea is to iterate over the range [1, N]. For every ith number, concatenate the binary representation of the number i using the Bitwise XOR property. Follow the steps below to solve the problem:
- Initialize two variables, l, and ans with 0, where l stores the current position of the bit in the final binary string of any ith number and ans will store the final answer.
- Iterate from i = 1 to N + 1.
- If (i & ( i – 1 )) is equal to 0, then simply increment the value of l by 1, where & is the Bitwise AND operator.
- After that, the left shift ans by l and then bitwise OR the result with i.
- After and traversing, print ans as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the decimal value by// concatenating the numbers from 1 to Nint concatenatedBinary(int n){ // Stores count of // bits in a number int l = 0; // Stores decimal value by // concatenating 1 to N int ans = 0; // Iterate over the range [1, n] for (int i = 1; i < n + 1; i++){ // If i is a power of 2 if ((i & (i - 1)) == 0) l += 1; // Update ans ans = ((ans << l) | i); } // Return ans return ans;}// Driver Codeint main(){ int n = 3; // Function Call cout << (concatenatedBinary(n)); return 0;}// This code is contributed by mohiy kumar 29 |
Java
// Java program for the above approachclass GFG{ // Function to find the decimal value by // concatenating the numbers from 1 to N static int concatenatedBinary(int n) { // Stores count of // bits in a number int l = 0; // Stores decimal value by // concatenating 1 to N int ans = 0; // Iterate over the range [1, n] for (int i = 1; i < n + 1; i++){ // If i is a power of 2 if ((i & (i - 1)) == 0) l += 1; // Update ans ans = ((ans << l) | i); } // Return ans return ans; } // Driver Code public static void main (String[] args) { int n = 3; // Function Call System.out.println(concatenatedBinary(n)); }}// This code is contributed by AnkThon |
Python3
# Python program for the above approach# Function to find the decimal value by # concatenating the numbers from 1 to N def concatenatedBinary(n): # Stores count of # bits in a number l = 0 # Stores decimal value by # concatenating 1 to N ans = 0 # Iterate over the range [1, n] for i in range(1, n + 1): # If i is a power of 2 if i & (i - 1) == 0: # Update l l += 1 # Update ans ans = ((ans << l) | i) # Return ans return(ans) # Driver Codeif __name__ == '__main__': n = 3 # Function Call print(concatenatedBinary(n)) |
C#
// C# program to implement// the above approach using System;class GFG{ // Function to find the decimal value by // concatenating the numbers from 1 to N static int concatenatedBinary(int n) { // Stores count of // bits in a number int l = 0; // Stores decimal value by // concatenating 1 to N int ans = 0; // Iterate over the range [1, n] for (int i = 1; i < n + 1; i++) { // If i is a power of 2 if ((i & (i - 1)) == 0) l += 1; // Update ans ans = ((ans << l) | i); } // Return ans return ans; } // Driver Code public static void Main () { int n = 3; // Function Call Console.WriteLine(concatenatedBinary(n)); }}// This code is contributed by sanjoy_62 |
Javascript
<script>//Javascript program to implement// the above approach// Function to find the decimal value by// concatenating the numbers from 1 to Nfunction concatenatedBinary(n){ // Stores count of // bits in a number var l = 0; // Stores decimal value by // concatenating 1 to N var ans = 0; // Iterate over the range [1, n] for (var i = 1; i < n + 1; i++){ // If i is a power of 2 if ((i & (i - 1)) == 0) l += 1; // Update ans ans = parseInt((ans << l) | i); } // Return ans return ans;}var n = 3;// Function Calldocument.write(concatenatedBinary(n));//This code is contributed by SoumikMondal</script> |
Output:
27
Time Complexity: O(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!
