Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1680.html

1680. Concatenation of Consecutive Binary Numbers (Medium)

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 109 + 7.

 

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1. 

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.

 

Constraints:

• 1 <= n <= 105

Related Topics:
Math

Solution 1.

Let f(n) be the answer. sum_len(a, b) = sum( len(i) | a <= i <= b) and len(i) is the number of bits in i.

For example: len(1) = 1, len(3) = 2, len(6) = 3. sum_len(1,4) = len(1) + len(2) + len(3) + len(4) = 1 + 2 + 2 + 3 = 8.

So we have

f(n)   = (1 << sum_len(2, n))   + (2 << sum_len(3, n))   + ... + ((n - 1) << sum_len(n, n)) + (n << 0)

// Example: f(4) = 11011100 = (1 << (2+2+3)) + (2 << (2+3)) + (3 << 3) +(4 << 0)

f(n-1) = (1 << sum_len(2, n-1)) + (2 << sum_len(3, n-1)) + ... + ((n - 1) << 0)

f(n) = (f(n-1) << len(n)) + n

Since f(0) = 0, we can iteratively build f(n).

f(0) = 0
f(1) = 1     = (f(0) << 1) + 1  // len(1) = 1
f(2) = 110   = (f(1) << 2) + 2  // len(2) = 2
f(3) = 11011 = (f(2) << 2) + 3  // len(3) = 2
...

// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int concatenatedBinary(int n) {
        long ans = 0, mod = 1e9+7;
        for (int i = 1; i <= n; ++i) {
            int len = 0;
            for (int j = i; j; j >>= 1, ++len);
            ans = ((ans << len) % mod + i) % mod;
        }
        return ans;
    }
};

Solution 2.

We spent O(logN) time for calculating the len. We can reduce it to O(1) with the help of __builtin_clz which returns the number of leading zeros for a number, so len = 32 - __builtin_clz(i).

// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int concatenatedBinary(int n) {
        long ans = 0, mod = 1e9+7;
        for (int i = 1; i <= n; ++i) ans = ((ans << (32 - __builtin_clz(i))) % mod + i) % mod;
        return ans;
    }
};

Or, with the observation that the len only increment when the i is a power of 2, we can increment len only when i has a single bit 1. We can check this via (i & (i - 1)) == 0 or __builtin_popcount(i) == 1.

// OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int concatenatedBinary(int n) {
        long ans = 0, mod = 1e9+7, len = 0;
        for (int i = 1; i <= n; ++i) {
            if ((i & (i - 1)) == 0) ++len;
            ans = ((ans << len) % mod + i) % mod;
        }
        return ans;
    }
};

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int concatenatedBinary(int n) {
          final int MODULO = 1000000007;
          long num = 0;
          int bits = 0;
          for (int i = 1; i <= n; i++) {
              if ((i & (i - 1)) == 0)
                  bits++;
              num = ((num << bits) + i) % MODULO;
          }
          return (int) num;
      }
  }
  
  ############
  
  class Solution {
      public int concatenatedBinary(int n) {
          final int mod = (int) 1e9 + 7;
          long ans = 0;
          int shift = 0;
          for (int i = 1; i <= n; ++i) {
              if ((i & (i - 1)) == 0) {
                  ++shift;
              }
              ans = (ans << shift | i) % mod;
          }
          return (int) ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
  // Time: O(NlogN)
  // Space: O(1)
  class Solution {
  public:
      int concatenatedBinary(int n) {
          long ans = 0, mod = 1e9+7;
          for (int i = 1; i <= n; ++i) {
              int len = 0;
              for (int j = i; j; j >>= 1, ++len);
              ans = ((ans << len) % mod + i) % mod;
          }
          return ans;
      }
  };
  

• class Solution:
      def concatenatedBinary(self, n: int) -> int:
          mod = 10**9 + 7
          ans = shift = 0
          for i in range(1, n + 1):
              if (i & (i - 1)) == 0:
                  shift += 1
              ans = (ans << shift | i) % mod
          return ans
  
  ############
  
  # 1680. Concatenation of Consecutive Binary Numbers
  # https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/
  
  class Solution:
      def concatenatedBinary(self, n: int) -> int:
          M = 10 ** 9 + 7
          s = []
          for i in range(1, n+1):
              s.append(str(bin(i)[2:]))
          
          s = "".join(s)
          
          return int(s,2) % M
  
  

• func concatenatedBinary(n int) (ans int) {
  	const mod = 1e9 + 7
  	shift := 0
  	for i := 1; i <= n; i++ {
  		if i&(i-1) == 0 {
  			shift++
  		}
  		ans = (ans<<shift | i) % mod
  	}
  	return
  }
  

• function concatenatedBinary(n: number): number {
      const mod = BigInt(10 ** 9 + 7);
      let ans = 0n;
      let shift = 0n;
      for (let i = 1n; i <= n; ++i) {
          if ((i & (i - 1n)) == 0n) {
              ++shift;
          }
          ans = ((ans << shift) | i) % mod;
      }
      return Number(ans);
  }
  
  

All Problems

All Solutions