Interview question about 01011011101111011111... sequence. What about calculus as a metric of code quality?
Tags: math, programming, algorithms, javascript
Published: 2021-12-02 11:32:49

## Table Of Contents
  * [Solution #1: Generators](#generators)
  * [Solution #2: Why should I care about powers of two and binary representations of digits?](#binary)
  * [Solution #3: Simplest possible](#simpest)
  * [About Time Complexity of **Solution #1**](#complexity)
  * [Calculus as a metric of code quality?](#calculus)

## Preface

It was a long time ago when I heard about this task in an interview. I have solved it by some algo that I'm not proud of. But this task is in my head and time by time I think about it and find better and better ways to solve it.
If you can see powers of two in the title of this article or any other way to solve it, please share it with us, leave any comments. Any thoughts can be useful.

Let's move to the solutions.

## Solution #1: Generators <a name="generators"></a>

I found it very fast because this way was preferred by my interviewer. Mostly it's not about solution of the task. You just need to know how generators work and that's it.
I think this is `O(N^2)` classical problem (or not?). I can show you the algo on TypeScript lang. It's like JavaScript but with types.


```typescript
export function* strangeZeroOneSequence(length: number): Generator<number> {
  for (let counter = 0; counter < length; counter++) {
    let iterator = 0;
    yield iterator;

    while (iterator <= counter) {
      yield 1;
      iterator++;
    }
  }
}
```

Computer programming it's constantly about test cases

```typescript
describe("Check strangeZeroOneSequence", () => {
  it("01 sequence", () => {
    const generator = strangeZeroOneSequence(1);
    const array = [...generator];
    expect(array).toStrictEqual([0, 1]);
  });
  it("01011011101111 sequence", () => {
    const generator = strangeZeroOneSequence(4);
    const array = [...generator];
    console.warn(array);
    expect(array.join("")).toBe("01011011101111");
  });
});
```

Ok, you can play with it by yourself and leave any comments about it.
I want to stop now with it, and you can look at the complexity estimation of this algo in the bottom of this article. I move to the solution #2.


## Solution #2: Why should I care about powers of two and binary representations of digits? <a name="binary"></a>

Because it's one direct way to solve it. Let's remember about powers of two in table view, but let's skip first power `2^0=1`


| Binary | `2^x`  | Decimal |
| ------ |:------:| -------:|
| 10     | `2^1`  |   2     |
| 100    | `2^2`  |   4     |
| 1000   | `2^3`  |   8     |
| 10000  | `2^4`  |   16    |
| 100000 | `2^5`  |   32    |
And etc.

Column "Binary" is exactly the pattern, but inverted by somehow. We need replace first `1` from the left to `0` and every next `0` to `1`. How can we do this, but without any loops? Is there any way?

> In the binary system, each digit represents an increasing power of 2, with the rightmost digit representing 20, the next representing 21, then 22, and so on. The value of a binary number is the sum of the powers of 2 represented by each "1" digit. For example, the binary number 100101 is converted to decimal form as follows [wiki link](https://en.wikipedia.org/wiki/Binary_number#Binary_counting)

![Binary to decimal](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3pwfn8w4u34aiof3f8m7.png)

Every binary number that looks like `1000...0` <- one from the beginning and bunch of zeros till the end, when it equals exact power of two `2^n`

|`2^n`|`2^(n-1)`|`2^(n-1)`|  ...  | `2^2` | `2^1` | `2^0` |
| ----|:-------:|:-------:| -----:| -----:| -----:| -----:|
|  1  |    0    |    0    |  ...  |   0   |   0   |   0   |

To find decimal we can sum all powers of two from `2^0` up to `2^n` where binary representation equals to 1

How to invert every item of binary number from `0` to `1` without any loop? Let's use math, because it works for the binary too!

|`2^n`|`2^(n-1)`|`2^(n-1)`|  ...  | `2^2` | `2^1` | `2^0` |
| ----|:-------:|:-------:| -----:| -----:| -----:| -----:|
|  1  |    1    |    1    |  ...  |   1   |   1   |   1   |
|  1  |    0    |    0    |  ...  |   0   |   0   |   0   |
|  0  |    1    |    1    |  ...  |   1   |   1   |   1   |

`(row 1)` => full set of ones
`(row 2)` => first term is one and rest are zeros
`(row 3) = (row 1) - (row 2)` => is our sequence!

Here is the solution:

```typescript
export const strangeZeroOneSequence = (length: number): string => {
  let [result, chunk] = ['', 0];
  // One single loop till the end O(N)
  for (let i = 0; i < length; i++) {
    chunk += Math.pow(2, i);
    // Just binary data casting, that's O(1)
    result += `0${chunk.toString(2)}`;
  }
  return result;
};


```

Test cases:

```typescript
describe("Check strangeZeroOneSequence", () => {
  it("01 sequence", () => {
    const result = strangeZeroOneSequence(1);
    expect(result).toBe("01");
  });
  it("01011 sequence", () => {
    const result = strangeZeroOneSequence(2);
    expect(result).toBe("01011");
  });
  it("010110111 sequence", () => {
    const result = strangeZeroOneSequence(3);
    expect(result).toBe("010110111");
  });
  it("01011011101111 sequence", () => {
    const result = strangeZeroOneSequence(4);
    expect(result).toBe("01011011101111");
  });
});

```

Complexity is definitely `O(N)`. As you can see, sometimes the binary format of numbers is more representative than it looks.


## Solution #3: Simplest possible <a name="simpest"></a>

I could start from this, but who's gonna read me if I create an article with just 10 lines of code? =)

```typescript
export function strangeZeroOneSequence(length: number): string {
  let [result, sequence] = ['', '01'];
  for (let i = 0; i < length; i++) {
    result += sequence;
    sequence += '1';
  }
  return result;
}
```

You can use test cases from 
Some of you already knew the answer from the beginning. Not anytime you have a simple and expressive solution.

Probably you have yours solution - would you share it?

---

### About Time Complexity of **Solution #1** <a name="complexity"></a>

Is it `O(N^2)`, or could we estimate it a little better? Yes we can and no, **we shouldn't**! Estimation `O(N^2)` is good enough.
You need to move to real math if you want to make a more precise estimation.
And I can give you just a little notch to open this shade for you. How can we estimate the time-complexity of this algo but with more accuracy than `O(N^2)`?
Let's make 2 sequences and then graphically visualize it. 

> `n` -> gap of zeros in the sequence
> `b` -> count of algo iteration that we save per every run

So we can make a plot, where `n`, `b` on `x`, `y` axes. Just two dimensional Decart system.

You can find data and graph [here on desmos](https://www.desmos.com/calculator/rvemcqioao)

![Discret data of iterations count](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/unppv8gz3bbrm4rdn7n1.png)

So, just activate second group to see the math function that predict the behavior per every point in our function space

![Math function of complexity](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/loq9u81zpfmr20vjv49l.png)
 
**And I have Calculus proof that this is the exact function.** 
Let's start from `f(x)` and antiderivative `F(x)`. It we want to find the work of this function in time space, it should be the definite integral of `F(x)` between 0 and 99 (range of `n` or better to call it `t`, time space of execution)

![Discrete and continuous functions have the same space](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ubbjx2pnl7t5i857sfnn.png)
 
You can see that this is the exact match, value of the integral = latest value in the `b` = 5049

And functions match in both spaces (discrete and continues) at any scale!

![Space match](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/akn0pzaucsbrwmt8hfrx.png)

## Calculus as a metric of code quality? <a name="calculus"></a>

It's very interesting and beautiful when you can find the the exact math function that express work that the program function has done. You can think about every function on your code as a pices of work that it has to be done. **Then you can think about optimization and bottle necs in the algo, based on the math!** There are so many ways of optimizations math functions!
Probably there is the whole area of analysis of computer program functions spaces. Do you know tools that can automatically analyze your program functions space and create some reports about it?
In case of **pure functions** we have `input space` map to `output space` of the program function. You can find correlation between `input space` and `output space` based on type signatures.
And test cases of your project can make this job, it can be very interesting report. Just think about it as a tool that can find every function, every method in your code, run it and aggregate statistics about complexity of the algo per every line of the code. And detected correlation between `input space` and `output space` can provide an infinity possible ways for optimization of any kind programs!
Probably [interpolation](https://en.wikipedia.org/wiki/Interpolation) techniques can give us the chance

What a piece of work!

---

Join me on:

[Twitter](https://twitter.com/oaiwty)
[YouTube](https://www.youtube.com/channel/UCeT2J4G8gAnBgE_BO5JmznQ)
[Github](https://github.com/nickovchinnikov)
[LinkedIn](https://www.linkedin.com/in/nikita-ovchinnikov-79aa25a9/)