Skip to content

Latest commit

 

History

History
90 lines (77 loc) · 2.22 KB

1680. Concatenation of Consecutive Binary Numbers.md

File metadata and controls

90 lines (77 loc) · 2.22 KB

1680. Concatenation of Consecutive Binary Numbers

the third one in Weekly Contest 218.

leetcode Daily Challenge on January 27th, 2021.

Difficulty : Medium

Related Topics : Math

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 10^9 + 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 <= 10^5

Solution

  • mine
    • Java
      • Runtime: 90 ms, faster than 84.45%, Memory Usage: 38 MB, less than 51.50% of Java online submissions 
        public int concatenatedBinary(int n) {
    long res = 0;
    int bitCount = 0;
    int mod = 1_000_000_007;
    for(int i = 1; i <= n; i++){
        if((i & (i - 1)) == 0){
            bitCount++;
        }
        res = ((res << bitCount) + i) % mod;
    }
    return (int)res;
}
  • the most votes
  • Runtime: 5 ms, faster than 99.77%, Memory Usage: 36 MB, less than 79.00% of Java online submissions 
    private static final int MOD = 1000000007;
private static final int[] aux = new int[100001];
private static int BASE = 0;

public int concatenatedBinary(int n) {
    if (aux[n] != 0) return aux[n];
    int i = 1;
    while (i < n && aux[i] != 0) i++;
    for (; i <= n; i++) {
        if (((1 << BASE) & i) != 0) BASE++;
        aux[i] = (int)((((long)(aux[i - 1]) << BASE) + i) % MOD);
    }
    return aux[n];
}