C++ | Must Know Method ✔ | Explained ✔
Understanding: In a binary represenatation, 1110 = 14 can be written as: 1100 + 10 = (11<<2) +  (10<<0) = 12+2 = 14.\n(All Binary Notation are in Bold.) \nExamp
Understanding: In a **binary represenatation**, **1110** = 14 can be written as: **1100** + **10** = (**11**<<*2*) +  (**10**<<*0*) = *12+2 = 14*.\n(All Binary Notation are in Bold.) \nExample:\nLets say n = *3*.\nSo, concatenation would be: **1 10 11 100**\nEach time we concatenate, we left shift our previous number by length of binary representation of that number.\nSo, at *1*, we have *1*.\nAt *2*, we have **1** **10**, (**1**<<*2*) + **10** = *4 + 2 = 6*,One left shifts twice to create space for the new number which has *2* bits in it. \nAt *3*, similarly, **110** **11**, 6 is left shifted twice, so* 6x2x2 = 24 + 3*(the new number) = *27*.\n\n```\nclass Solution {\npublic:\n    const int mod = 1e9+7;\n    int concatenatedBinary(int n) {\n        long ans = 0;\n        int length = 0;\n        for (int i = 1; i <= n; ++i) {\n            //Length increases on each power of two.\n            if ((i&(i - 1)) == 0) \n                ++length;\n            //Left shift by that length.\n            ans = ((ans << length) % mod + i) % mod;\n            cout << length << endl;\n        }\n        return ans;\n    }\n};\n```\n
['Math', 'Bit Manipulation', 'C', 'C++']