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.
Programming Praxis 
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:
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:
@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]@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. :-)
@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
nby preventing overflow, since(A + B) mod C = (A mod C + B mod C) mod Cand(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:
@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; }<?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); } ?>