1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int concatenatedBinary(int n) {
        long ans = 0;
        int length = 0;
        int mod = (int) 1e9 + 7;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                length += 1;
            }
            ans = ((ans << length) | i) % mod;
        }
        return (int) ans;
    }
}

本质就是要给后面的腾位置. 问题是如何知道新来的数字的binary的长度? 由于是连续的把1-n的数字给concatenate起来. 当我们遇到2的倍数的时候, 说明是多了一个digit在binary中. 比如一开始是1, 长度是1, 等到2的时候长度变为了2, 等到4的时候长度为3… 那如何判断是否是2的倍数呢? 之前总结过, 就是num & (num - 1)是否等于0, 如果等于0就说明是2的倍数. 于是我们先把result往左移动相应的步数, 然后把当前的值or到最低的几位上即可.

还有一个问题就是我们进行一次操作就mod一下, 这样做的结果是对的吗? 答案是没问题的. 比如我们进行到一个数字x, 我们mod一下得到y, 商是z. 那就有x = z * modulo + y. 然后我们把y移动n位得到一个数字yn再加个数字. 那如果把x移动n位再做modulo, 我们会发现等式右侧第一项处以modulo是可以除尽的, 而第二项乘上2的n次方不就是yn, 再加个数字就和只用yn再加个数字一样. 等于是此时yn + 一个数字然后做modulo的答案就是x乘上2的n次方加上一个数字做modulo的答案.

于是我们发现这样做是没问题的.

时间复杂度: O(n)
空间复杂度: O(1)