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
Auto comment: topic has been updated by slayer_coder (previous revision, new revision, compare).
Auto comment: topic has been updated by slayer_coder (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
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/i5oS23
Hope this helps.
https://oeis.org/A047778
that was what i did but I think that is O(n) is'nt it please correct if i am wrong
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
$$$ 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.