slayer_coder's blog

Google Sample Question for google online coding challenge
By slayer_coder, history, 3 years ago, In English

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

  • Vote: I like it
  • -21
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by slayer_coder (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by slayer_coder (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

what i did was a very poor solution of complexity O(n) which could only pass 50 % of the cases

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

and plz don't think i am cheating it is a sample question which can be found if you register for online coding challenge

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

https://oeis.org/A047778

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that was what i did but I think that is O(n) is'nt it please correct if i am wrong

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        $$$ 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.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now if you want to calculate for lets say 15. It is simply

    Can you explain a little bit more?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply