[Python] O(n) and O(log^2 n) fast and short, explained
One way to solve this problem in competition is just create very long binary string and then find result of division by 10**9 + 7 and it will work fine. However
One way to solve this problem in competition is just create very long binary string and then find result of division by `10**9 + 7` and it will work fine. However in interview setup it is not the best idea and I prefer more honest way. Let us look at first several `n` to see how it works:\n`1`\n`110`\n`11011`\n`11011100`\n\nLet us try to find answer to `n`, using information about `n-1`. `110` = `1 * 100 + 10` (all in binary representation), `11011 = 110 * 100 + 11`, `11011100 = 11011 * 1000 + 100` and so on. We can see that on each step we need to multiply number by **lenght** of new number and add new number (and use `%M`) and that is all!\n\n**Complexity**: time complexity is `O(n)`, space is `O(1)`.\n\n```\nclass Solution:\n    def concatenatedBinary(self, n):\n        ans, M = 0, 10**9 + 7\n        for x in range(n):\n            ans = (ans * (1 << (len(bin(x+1)) - 2)) + x+1) % M\n        return ans \n```\n\n**Further thoughts** When you found `O(n)` solution, you should ask a question, can you do better? Here I had very strong intuition that you can do it faster and I came up with `O(log^2 n)` solution. Then I checked discussions and there is in fact at least two solutions with this complexity: one uses idea of geometrical progressions: idea behind is the following: we can see that in binary representation of desired number there will be `O(log n)` sequences of ones with equal gaps for each of `O(log n)` lengths of numbers. You can find this solution in discussion, I will code my own version if I have time. Another solution using matrix multiplications and I was very impressed to see it.\n\n### Faster solution with O(log^2 n) complexity\n\nIt is easier to chose some `n` and go into details about this `n`. Let us choose `n = 54` and discuss how my algorithm works:\n\nFunction `bin_pow` will return powers of `2`, which sum to given number, for example `bin_pow(37) = [1, 4, 32]`, because `1 + 4 + 32 = 37`.\n\nNow, we have `n = 54`, and we have:\n1. `1` number with length `1`: just `1`\n2. `2` numbers with length `2`: `10, 11`\n3. `4` numbers with length `3`: `100, 101, 110, 111`.\n4. `8` numbers with length `4`: `1000, ..., 1111`\n5. `16` numbers with length `5`: `10000, ..., 11111`.\nNow, we have 23 more numbers and we keep to split them into groups:\n6. `16` numbers with lenght `6`, which **start with** `10....`, that is `100000, 100001, ... 101111`. Why we choose `16` of them? Because it is the biggest group we can take such that this group is full: given start we have all possible endings.\n7. `4` numbers with length `6`, which **start with** `1100`, that is `110000, 110001, 110010, 110011`\n8. `2` numbers with length `6`, which **start with** `11010`, that is `110100` and `110101`.\n9. `1` number with length `6`: `110110`, which is equal to `54`, our last number.\n\nWe will keep lenghts of our groups in list `B`, so we have:\n`B = [1, 2, 4, 8, 16, 16, 4, 2, 1`]\n\nWe will keep length of numbers in each group in list `C`, so we have:\n`C = [1, 2, 3, 4, 5, 6, 6, 6, 6]`\n\nSo far we have the following picture:\n\n`[1][10 11][100 101 110 111] ...   [110000, 110001, 110010, 110011], [110100, 110101], [110110]`\n\nWe will keep starting places of each group in list `D`, in our case we have:\n`D = [266, 262, 250, 218, 138, 42, 18, 6, 0]`.\nLet us look from the end: last group we do not need to multiply by anything, previous group has `1` number with length `6`, so we need to multiply it by `2^6`. Next we have `2*6 + 1*6` shift, `4*6 + 2*6 + 1*6`, `16*6 + 4*6 + 2*6 + 1*6`, `16*5 + 16*6 + 4*6 + 2*6 + 1*6` and so on: it can be done efficiently, using `accumulate` function in python.\n\nFinal step is to iterate over our groups and evaluate number modulo `10**9 + 7` in each group:\n\nLet us look at group `[110000, 110001, 110010, 110011]` for better underastnding. This group will be somewhere in the middle of number, like `...[110000, 110001, 110010, 110011]...` and we need to understand what impact it has on our number, we need several values:\n1. Place, where this group is located, for this we use `D` list, `d` for given group.\n2. Lenth of elements in each group, for this we use `C` list, `c` for given group.\n3. Number of elements in our group, for this we use `B` list, `b` for given group.\n4. Also we need to now, from which element we start, in our case it is `110000`, we can evaluate it as `a - b + 1`, where `a` is corresponding element in `accumulate(B)`: here we have `accumulate(B) = [1, 3, 7, 15, 31, 47, 51, 53, 54]` and `51-4 + 1 = 48` is current number we start with, `a` for given group\n\nFinally, we need to do some mathematics: we need to evaluate sum:\n`[(a-b+1) * 2^(b*c) + (a-b+2)*2^(b*(c-1)) + ... +  (a-b + c-1) * 2^(b*1) + (a-b + c) * 2^(b*0)]*2^d`.\n\nThis formula can be written in closed form! It is almost like sum of geometrical progression, but in fact, sum of several of them which lead us to closed form solution. We also need to work using modular arithmetic, so we use powerful `pow` python function. In my notation `t1 = [2^(bc) - 1] % MOD` and `t2 = [1/(2^c - 1)] % MOD`. Here we use Fermat\'s little theorem to evaluate inverse number in modular arithmetic. \n\n**Complexity**: time complexity of evaluating `B, C, D` lists is just `O(log n)`. However when we work with `pow` function, complexity to evaluate sum in each group will be also `O(log n)`, which leasd to `O(log^2 n)` time complexity. Space complexity is `O(log n)`.\n\n\n```\nclass Solution:\n    def concatenatedBinary(self, n):\n        def bin_pow(num): return [1<<i for i, b in enumerate(bin(num)[:1:-1]) if b == "1"]\n        ans, MOD, q = 0, 10**9 + 7, len(bin(n)) - 3\n\n        B = bin_pow((1<<q) - 1) + bin_pow(n - (1<<q) + 1)[::-1]\n        C = list(range(1, q+1)) + [q+1]*(len(B) - q)\n        D = list(accumulate(i*j for i,j in zip(B[::-1], C[::-1])))[::-1][1:] + [0]\n        \n        for a, b, c, d in zip(accumulate(B), B, C, D):\n            t1 = pow(2, b*c, MOD) - 1\n            t2 = pow(pow(2, c, MOD)-1, MOD - 2, MOD)\n            ans += t2*((a-b+1+t2)*t1-b)*pow(2, d, MOD)\n\n        return ans % MOD\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]