### ayush2800's blog

By ayush2800, history, 11 days ago, Can somebody plz help me out with the following question-

You have been given a number say n and you have to do this following operation- find the resultant number which is formed by appending binary number of the first n positive numbers.

1<=n<=10^9

suppose n=4

1 in binary is 1

2 in binary is 10

3 in binary is 11

so finally the number formed is 1 10 11 or 11011->27's binary representation therefore the resultant number is 27

sorry for my bad explanation of the question  Comments (19)
 » Auto comment: topic has been updated by ayush2800 (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ayush2800 (previous revision, new revision, compare).
 » what i did was a very poor solution of complexity O(n) which could only pass 50 % of the cases
 » and plz don't think i am cheating it is a sample question which can be found if you register for online coding challenge
 » 11 days ago, # | ← Rev. 2 →   since n can be as large as 10^9 then simple O(n) solution would not work.Since maximum bits in a number can be 31 only we can think of solution which deals with bits.Suppose you have some prevans calculated for numbers upto i bits then you want to concatenate all the numbers with (i+1) bits then you can see tot = 2^(i+1) — 2^i are the total numbers with i+1 bits which will cause a shift of tot*(i+1) places so we will add 2^(tot*(i+1)) in our previous ans now we have to calculate the ans for numbers between them. You can see that the ans for them is making a Arithmetic-Geometric series which can be calculated using formula(do some work on copy).For example : suppose we want to find for 8 to 15 we can see ans = 8*2^(tot*i-1*i) + 9*2^(tot*i-2*i)...........where i(in this case = 4) is number of bits we are at.Ac code:- https://ideone.com/i5oS23Hope this helps.
 »
•  » » that was what i did but I think that is O(n) is'nt it please correct if i am wrong
•  » » » 11 days ago, # ^ | ← Rev. 3 →   You could see the recursive formula imagine floor value of log2(n) being constant, considering that you could find the range sum formula. You could also apply matrix exponentiation for that recursive sequence to calculate the terms required for that constant value and now new base terms required for new constant value or just previous floor +1 you could say If there was some relationship between log(x) and log(x-1) which was dependent somewhat linearly then we could have apply matrix exponentiation directly instead of parts as we are doing above
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   $F(n) = c * F(n-1) + (n - 1) + 1$ $[F(n) , n, 1] = [[c,1,1],[0,1,1],[0,0,1]] \times [F(n-1),(n-1),1]$ c is the constant log value here this is the matrix if needed, according to me matrix exponentiation is less prone to errors as we just need to use template instead of AGP.
 » I suspect there is something you are not telling, because if $n$ is $10^9$, the answer will be about $30 \cdot 10^9$ bits long: a lot bigger than the typical output size in competitive programming problems.
•  » » i'll just post a screenshot of the same
•  » » yeah ofcourse you have to print the number mod 10^9+7
•  » » It was modulo 1e9+7.
•  » » » how did you solve it
 » If you notice the number of bits... for number from $1$ to $n$. They are $1, 2, 2 ,3,3,3,3,4,4,4,4,4,4,4,4.....$ i.e $1$ time $1$, $2$ times $2$, $2^2$ times $3$, $2^3$ times $4$ and so on....Now if you want to calculate for lets say 15. It is simply $15+ 14*(2^4)+ 13*(2^8)+ 12*(2^{12})........+8*2^{28}+....+7*2^{32+0}+6*2^{32+3} + 5*2^{32+6}...$ so on. This can be calculated for each number of bits using some tedious calculations of arithmetico geometric progression.
•  » » Now if you want to calculate for lets say 15. It is simplyCan you explain a little bit more?
•  » » » See appending to the left means shifting the bits by the amount of the sum of the number of bits to the right of it. when you add 15, then add 14 to the left of it. 14 is shifted 4 steps to right, so $14*2^{4}$ and this will continue as more bits gets added. Hope this clears
•  » » » » got it, thanks!
 » You can go from bit 0 to 30, then take the numbers from 1 << bit to min(n, 1 << (b + 1)). Previous ans becomes ans*(2^(len*number_of_terms)). let number of terms be t. Now, increment for present ans is sum of (2^bit + i)*2^(t- i — 1) with i from 0 to t — 1. This can be simplified with Gp to get the final expression.