# SPOJ Problem: Adjacent Bit Counts

### A Little Background

I was trying to solve this problem on SPOJ. It’s a dynamic-programming problem. I tried to find some recursive relation. I spent hours. But no breakthrough.

I even tried looking for hints in comments and I came to know it’s a 3D dynamic-programming problem. Some of the users were even able to reduce it to a 2D technique.

Then I realized I need to rethink the entire approach. So somehow, I started treating it like a combinatorics problem and I landed on a solution — a formula that guarantees linear time execution. I love moments like these when you solve an interesting problem with an uncommon approach. And that’s why I am writing this post.

### The Problem

The problem involves dealing with bit strings. A bit string is basically a sequence where each term can have value either $0$ or $1$.

Usually, bit strings are represented without commas. So the bit string $1,0,0,1,0$ is abbreviated as $10010$.

Now we define a function $f(s)$ which takes a bit string $s = x_1 x_2 \ldots x_n$ and gives the output:

This function is what they call the adjacent bit count of $s$. This function basically tells us the number times the bit string $11$ appears in $s$.

E.g.   $f(101)=0$,   $f(1011)=1$,   $f(111)=2$,   $f(110111)=3$.

Now we’re ready to state our problem.

Given positive integers $n$ and $k$, find the number of bit strings $s$ of length $n$ which satisfies $f(s)=k$.

For example, let $n=5$ and $k=2$. The possible bit strings are $11100$,   $01110$,   $00111$,   $11011$,   $10111$,   $11101$. So our answer is $6$.

### Solution

We are given the fixed values $n$ and $k$. We introduce a variable value $a$ which we define as the number of continuous blocks of 1-bits in a bit string. Now onwards, we will refer to this as 1-block.

For example, $101110011$ has $a=3$ and $1010101$ has $a=4$.

If we fix the value of $a$, our problem becomes simpler as we will see later. We then have to calculate adjacent bit count for each possible value of $a$ and then sum them to obtain our final answer.

Before we jump to the actual solution, we need to observe a few things.

Let $m_1, m_2, \ldots ,m_a$ be the number of 1-bits in the $a$ 1-blocks from left to right respectively. E.g., for $101101$ we have $m_1 = 1$, $m_2 = 2$ and $m_3=1$.

Note the following points:

In a 1-block containing $m_i$ 1-bits, the bit string $11$ appears $m_i - 1$ times. This gives adjacent bit count for a single 1-block. So for the entire bit string, we must have $k = \sum_{i=1}^{a}\left(m_i -1\right) = {\sum m_i }-a$. So we get

Since a bit string consists of only zeros and ones, we get

Since $k \geq 1$, we must have at least one 1-block, and hence $a\geq1$. Also note that we must have at least $a-1$ 0-bits for separating the 1-blocks. This gives $a-1 \leq n-k-a \Rightarrow a \leq \frac{n-k+1}{2}$. So the range of $a$ is

where $\left[x\right]$ denotes the floor function.

Now we move to the actual solution.

For a fixed value of $a$, we employ Beggar’s Method to our rescue. We take an empty bit string and break our problem into two parts.

Number of ways to fill 1-bits in the bit string: We have $k+a$ 1-bits, which we want to distribute in $a$ 1-blocks, which are currently empty. Number of ways to fill 0-bits in the bit string: We have $n-k-a$ 0-bits, which we want to distribute in the gaps between the 1-blocks.

So, for fixed $a$, our answer will be the product of above two values. Our final answer will be sum of these products.

#### Filling 1-bits

Imagine our $a$ 1-blocks as $a$ empty buckets lined up in a row from left to right, with their positions fixed. We need to find the number of ways we can distribute $k+a$ available 1-bits in them.

But we have to keep in mind that none of the bucket remains empty. So first, lets put one 1-bit in each of the buckets. Now, we have to distribute the remaining $k$ 1-bits in whatever way we wish.

Let $m_1, m_2, \ldots ,m_a$ be the distribution of remaining $k$ 1-bits in the buckets from left to right, respectively.

By Beggar’s Method, we get

#### Filling 0-bits

We have $a$ buckets, which gives us $a+1$ gaps to fill zeros in.

The first and the last gaps can remain empty. But the inner $a-1$ gaps must have at least one 0-bit, otherwise we will have less than $a$ 1-blocks which contradicts that we have $a$ blocks.

So we distribute one 0-bit in each of the inner gaps. Now we can freely distribute the remaining $n-k-a-\left(a-1\right) = n-k-2a+1$ 0-bits in $a+1$ gaps.

Let $x_1, x_2, \ldots , x_{a+1}$ be the distribution of remaining 0-bits in gaps. Then we have to solve

Applying Beggar’s Method, we get

As discussed earlier, our final answer is the summation of product of the binomial coefficients obtained in $\left(1\right)$ and $\left(2\right)$.

### Conversion To Code

To achieve linear runtime, it’s clearly visible that we have to run a for loop on $a$, the number of 1-blocks. In each pass of loop we have to calculate the product of binomial coefficients in constant time.

But the usual dynamic programming method takes $\mathcal{O}\left( q^2 \right)$ time for calculating $^{q}C_{r}$. But we can do it in constant time if we know the binomial coefficients in last pass. We do it using the following formula

Applying the above formula on the binomial coefficient in $\left(1\right)$, we get

For the binomial coefficient $\left(2\right)$, we substitute $p=n-k+1$ so as to make it look cleaner. ${^{n-k+1-a}C_{a}}$ becomes ${^{p-a}C_{a}}$. Using identity $\left(4\right)$ on this, we get

Note that the initial values of these coefficients i.e. when $a=1$, are $1$ and $n-k$ respectively. Keeping this in mind and using equations $\left(3\right)$ and $\left(6\right)$, this is what our final code solution looks like.

As you can see, the for loop runs $p/2$ times. Hence, the time complexity of program is $\mathcal{O}\left(n-k\right)$.

You can find the complete program here.