Krammer's blog

https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/ from Amazon

Thinking process:

Very simple. Just like the diagram below. We start from 1, keep doing the left-shift to our prefix, and then append a new number.

Here is the code.

 1class Solution {
 2public:
 3    typedef long long ll;
 4    int ans;
 5    int MOD = 1e9 + 7;
 6    int N;
 7    int bits(int x) {
 8        int ret = 0;
 9        while (x) {
10            ret++;
11            x = x >> 1;
12        }
13        return ret;
14    }
15    void dfs(ll pre, int cur) {
16        if (cur == (N + 1)) {
17            ans = pre;
18            return;
19        }
20        int b = bits(cur);
21        pre = ((pre << b) % MOD + cur) % MOD;
22        dfs(pre, cur+1);
23    }
24    int concatenatedBinary(int n) {
25        N = n;
26        dfs(0, 1);
27        return ans;
28    }
29};

Editorial: LeetCode 1680 Concatenation of Consecutive Binary Numbers