tags: leetcode Medium Math Bit Manipulation Simulation

1680.Concatenation Of Consecutive Binary Numbers

Description

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$.

Examples

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 $10^9 + 7$, the result is 505379714.

Constraints:

• $1\leq n\leq 10^5$

Code

int concatenatedBinary(int n) {
    int mod = 1e9 + 7;
    long ans = 0;
    int size = 0;
    for (int i = 1; i <= n; i++) {
        if ((i & (i - 1)) == 0)
            size++;
        ans <<= size;
        ans |= i;
        ans %= mod;
    }
    return ans;
}

Complexity

Space	Time
$O(1)$	$O(n)$

Result

• Runtime: 31 ms, 75 %
• Memory: 5.3 MB, 100 %

Notes

How to get bit-size of numbers

• Method 1

int GetBitSize(int number){
    temp = number;
    count=0;
    while(temp!=0){
        temp = temp>>1;
        count++;
    }
    return count;
}

Directly count number length during each turn shifting number right 1 bit.
Its complexity is

Space	Time
$O(1)$	$O(log(n))$

• Method 2

int GetBitSize(int number){
    int count = 0;
    for(int i = 1 ; i <= number ; i++){
        if ((i & (i - 1)) == 0)
            count++;
    }
    return count;
}

Just like Kernighan’s Algorithm. Kernighan’s Algorithm wants to count how many set bit in a given number.
It uses the feature that AND operation of number and number - 1 will set the less significant setting bit. Like

Number	Binary
N = 12	1100
N-1 = 11	1011
N & (N-1) = 8	1000

After then, setting new number as number & (number - 1), until the number become zero.
If we inverse this operation, we can find the length of binary increase as the number carries.
It is like the behavir of less significant setting bit works, only become zero as it carry(10...0 & 01...1)

Number	Binary
N = 8	1000
N-1 = 7	0111
N & (N-1) = 0	0000

Its complexity is

Space	Time
$O(1)$	$O(n)$