# 1680. Concatenation of Consecutive Binary Numbers¶

## Approach 1: Naive¶

• Time: $O(n\log n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int concatenatedBinary(int n) { constexpr int kMod = 1'000'000'007; long ans = 0; for (int i = 1; i <= n; ++i) ans = ((ans << numberOfBits(i)) % kMod + i) % kMod; return ans; } private: int numberOfBits(int n) { return log2(n) + 1; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int concatenatedBinary(int n) { final int kMod = 1_000_000_007; long ans = 0; for (int i = 1; i <= n; ++i) ans = ((ans << numberOfBits(i)) % kMod + i) % kMod; return (int) ans; } private int numberOfBits(int n) { return (int) (Math.log(n) / Math.log(2)) + 1; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def concatenatedBinary(self, n: int) -> int: kMod = 1_000_000_007 ans = 0 def numberOfBits(n: int) -> int: return int(math.log2(n)) + 1 for i in range(1, n + 1): ans = ((ans << numberOfBits(i)) + i) % kMod return ans 

## Approach 2: Increase length gradually¶

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int concatenatedBinary(int n) { constexpr int kMod = 1'000'000'007; long ans = 0; int numberOfBits = 0; for (int i = 1; i <= n; ++i) { if (__builtin_popcount(i) == 1) ++numberOfBits; ans = ((ans << numberOfBits) % kMod + i) % kMod; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int concatenatedBinary(int n) { final int kMod = 1_000_000_007; long ans = 0; int numberOfBits = 0; for (int i = 1; i <= n; ++i) { if (Integer.bitCount(i) == 1) ++numberOfBits; ans = ((ans << numberOfBits) % kMod + i) % kMod; } return (int) ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def concatenatedBinary(self, n: int) -> int: kMod = 1_000_000_007 ans = 0 numberOfBits = 0 for i in range(1, n + 1): if i.bit_count() == 1: numberOfBits += 1 ans = ((ans << numberOfBits) + i) % kMod return ans