# decimal value of the number formed by concatenating the binary representations of first n natural numbers

Given a number n, find the decimal value of the number formed by concatenating the binary representations of first n natural numbers.

Also, n can be as big as 10^9 and hence logarithmic time approach is needed.

Eg: n=`4`, Answer = `220`

Explanation: Number formed=`11011100` (`1=1`,`2=10`,`3=11`,`4=100`). Decimal value of `11011100`=`"220"`.

The code I am using below only works for first integers N<=15

```    String input = "";
for(int i = 1;i<=n;i++) {
input += (Integer.toBinaryString(i));
}
return Integer.parseInt(input,2);
```

Note that working with string representation is not necessary (moreover, is not useful after task changing). Look at approach with bitwise arithmetics (Python, but principle is the same)

With new condition concerning modulo 1000000007 we have just add modulo operation to result calculation line at every step, because shift left and or-ing is equivalent to multiplication by power of two and adding, these operations are obeyed to equivalence relations for modulo properties. Note that intermediate results don’t exceed `1000000007*n`, so long type is suitable here for reasonable n values.

```n = 100
size = 0   #bit length of addends
result = 0   # long accumulator
for i in range(1, n + 1):
if i & (i - 1) == 0:    #for powers of two we increase bit length
size += 1
result = ((result << size) | i) % 1000000007   #shift accumulator left and fill low bits with new addend
print(result)
```

variant without bitwise operations:

```pow2 = 1
nextpow = 2
result = 0   # long accumulator
for i in range(1, n + 1):
if i == nextpow:    #for powers of two we increase bit length
pow2 = nextpow
nextpow = nextpow * 2
result = (result * pow2  + i) % 1000000007  #shift accumulator left and fill low bits with new addend
```