[Go] O(n) with explanation
The rule described means every time left-shift, then add the number\n\n\nnumber = 1, string = 1\nnumber = 2, string left shift 2 bits = 100, adds number 2 becom
The rule described means every time left-shift, then add the number\n\n```\nnumber = 1, string = 1\nnumber = 2, string left shift 2 bits = 100, adds number 2 becomes 110\nnumber = 3, string left shift 2 bits = 11000, adds number 3 beomces 11011\n...\n```\n\nThe technique is to use bit-wise operation to find number of digits for the number, then do left-sift and add number. Also, add number mean bit-wise operation `or`.\n\nupdate at 1/28, original code find digits is not efficient, change to new one\n\n```golang\nfunc concatenatedBinary(n int) int {\n\tnum, digits := 1, 1\n\tvar ans int\n\tmod := int(1e9 + 7)\n\n\tfor ; num <= n; num++ {\n        if num == 1 << digits {\n\t\t\tdigits++\n\t\t}\n\n\t\tans = ans << digits\n\t\tans |= num\n\n\t\tans = ans % mod\n\t}\n\n\treturn ans\n}\n```\n\noriginal\n\n```golang\nfunc concatenatedBinary(n int) int {\n\tmod := int64(1e9 + 7)\n\tvar ans int64\n\n\tfor i := 1; i <= n; i++ {\n\t\tsize := digits(i)\n\t\tans = ((ans << size) | int64(i)) % mod\n\t}\n\n\treturn int(ans)\n}\n\nfunc digits(i int) int {\n\tvar shift int\n\n\tfor shift = 31; (1<<shift)&i == 0; shift-- {\n\t}\n\n\treturn shift + 1\n}\n```
['Go']