Binary Concatenation

July 14, 2020

We have an interview question today:

The concatenation of the first four integers, written in binary, is 11011100; that is, 1 followed by 10 followed by 11 followed by 100. That concatenated number resolves to 220. A similar process can convert the concatenation of the first n binary numbers to a normal decimal number.

Your task is to compute the nth binary concatenation in the manner described above; report the result modulo 109+7, because the result grows so quickly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

7 Responses to “Binary Concatenation”

  1. Daniel said

    Here are two solutions in Python, the first relying on string concatenation and the standard library’s binary/decimal conversion functions, and the second using @programmingpraxis’ numerical approach.

    def bconcat1(n):
        return int(''.join(bin(x)[2:] for x in range(1, n + 1)), 2) % (10 ** 9 + 7)
    
    def bconcat2(n):
        s, p, d = 0, 1, 10 ** 9 + 7
        for i in range(1, n + 1):
            p <<= i == p
            s = ((s * p) + i) % d
        return s
    
    for x in range(1, 10):
        print(f'{x} {bconcat1(x)} {bconcat2(x)}')
    

    Output:

    1 1 1
    2 6 6
    3 27 27
    4 220 220
    5 1765 1765
    6 14126 14126
    7 113015 113015
    8 1808248 1808248
    9 28931977 28931977
    
  2. Antonio said

    My first post here! I did this in C.

    Code:

    #include <stdio.h>
    #include <conio.h>
    #include <math.h>
    
    int solve(int a){
        int ret;
        //starting at 0, concatenate each int to the end of ret up to a
        for(int i = ret = 0; i <= a; i++) ret = bitcat(ret, i);
    
        return ret % (int)(pow(10, 9) + 7);
    }
    
    int main(){
        // test numbers 0 - 10
        for(int i = 0; i < 10; i++){
            printf("%d -> %d\n", i, solve(i));
        }
        getch(); return 0;
    }
    
    int bitcat(int a, int b){
        // make room for b at the end of a
        for(int i = b; i; i >>= 1) a <<= 1;
    
        // add b to the end
        return a | b;
    }
    

    Output:

    0 -> 0
    1 -> 1
    2 -> 6
    3 -> 27
    4 -> 220
    5 -> 1765
    6 -> 14126
    7 -> 113015
    8 -> 1808248
    9 -> 28931977
    
  3. matthew said

    @Antonio: nice solutiion, but you have to take the modulus each time around the loop rather than just at the end, to avoid overflow with intermediate values.

    A nice way of avoiding all those divisions is to use Montgomery multiplication, https://en.wikipedia.org/wiki/Montgomery_modular_multiplication:

    # Extended Euclidean algorithm
    def egcd (a,b):
        a0 = a; b0 = b
        x,y,z,w = 1,0,0,1
        while b != 0:
            q,r = divmod(a,b)
            a,b =  b,r
            x,y,z,w = z,w,x-q*z,y-q*w
        return a,x,y
    
    N = 10**9+7
    R = 1<<N.bit_length()
    (d,R0,N0) = egcd(R,N)
    R0 = R0%N
    N0 = (-N0)%R
    assert(R*R0-N0*N == 1)
    
    def convert(a): return a*R%N
    def unconvert(a): return a*R0%N
    
    def mmult(a,b):
        T = a*b
        m = T%R*N0%R
        t = (T + m*N)//R
        if (t >= N): t -= N;
        return t
    
    def concat(n):
        a = 0 # Accumulate result in a
        l,x = 0,R%N # Current bit length & converted multiplication factor
        k = R%N # convert(i)
        for i in range(1,n+1):
            if i.bit_length() != l:
                l += 1
                x += x
                if x >= N: x -= N
            assert(x == convert(2**i.bit_length()))
            assert(k == convert(i))
            a = mmult(a,x)
            a += k
            if a >= N: a -= N
            k += R%N
            if k >= N: k -= N
        return unconvert(a)
    
    print([concat(i) for i in range(16)])
    # [0, 1, 6, 27, 220, 1765, 14126, 113015, 1808248, 28931977, 462911642,
    #  406586234, 505379714, 86075381, 377206103, 35297621]
    
  4. Antonio Leonti said

    @matthew I believe we just interpreted the problem differently. I read it as, find the result, “whatever that may be,” then finally report it modulo 10^9+7. Thus I am doing “raw” binary concatenation then only taking the modulus once I have my final number. Perhaps my interpretation is wrong, though, in a “common sense” kind of way.

    Montgomery multiplication is going a bit over my head at the moment. Seems like the kind of thing I enjoy learning about, nonetheless, so thank you for sharing. :-)

  5. Daniel said

    “@matthew I believe we just interpreted the problem differently.”
    -@Antonio

    @Antonio, I believe that @matthew’s comment does not arise from a different interpretation, but is rather a suggestion that the modulus operation can be applied more frequently to get the desired answer for large n by preventing overflow, since (A + B) mod C = (A mod C + B mod C) mod C and (A * B) mod C = (A mod C * B mod C) mod C. For the bit shifting, the latter equation would apply since the operation is equivalent to multiplying by 2.

    Here’s an example in C, followed by usage with a large n (much larger than would be required for overflow without the intermediate modulus operations).

    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #define DIVISOR 1000000007
    
    int main(int argc, char* argv[]) {
      assert(argc == 2);
      int n = atoi(argv[1]);
      assert(n >= 0);
      int result = 0;
      for (int i = 1; i <= n; ++i) {
        for (int j = i; j; j >>= 1) {
          result = (result << 1) % DIVISOR;
        }
        result = (result + i) % DIVISOR;
      }
      printf("%d\n", result);
      return EXIT_SUCCESS;
    }
    

    Example usage:

    $ ./a.out 16777216
    602314637
    
  6. Daniel said

    @Antonio, the same idea applies to your solution by adding a modulus operation to lines 23 and 26, with the bitwise or changed to an addition.

    int bitcat(int a, int b){
        for(int i = b; i; i >>= 1) a = (a << 1) % 1000000007;
        return (a + b) % 1000000007;
    }
    
  7. Hakan said
    <?php
    
    function concatenateBinaryNumbers($n){
    	// Prepare an array with integers from 1 to n
    	$m = 1;
    	do {
    		$array[] = $m;
    		$m += 1;
    	} while ($m <= $n); 
    
    	// Prepare a string
    	$concatenated = '';
    
    	// Loop through the array 
    	foreach ($array as $number) {
    		// Convert each integer to a binary string and concatenate it to the prepared string
    		$concatenated .= decbin($number);
    	}
    
    	// Convert the concatenated string back to decimal format
    	$number = bindec($concatenated);
    	$number_modulated = $number % ((10 ** 9) + 7);
    
    	echo $n.'. '.$number.' mod 10^9 + 7 = '.$number_modulated.'<br>'; 
    
    
    }
     
    for ($i=1; $i < 16; $i++) { 
    	concatenateBinaryNumbers($i);
    }
    
    
    ?>
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: