Count the Divisible Numbers
Tags: javascript, codewars, kata, testing
Published: 2019-12-06 04:09:00

---
title: Count the Divisible Numbers
published: true
date: 2019-11-25 00:00:00 UTC
tags: Javascript,Codewars,Kata,Testing
canonical_url: http://www.petecorey.com/blog/2019/11/25/count-the-divisible-numbers/
---

Let’s try our hand at using a property test driven approach to solving a Codewars code kata. The kata we’ll be solving today is [“Count the Divisible Numbers”](https://www.codewars.com/kata/count-the-divisible-numbers/train/javascript). We’ll be solving this kata using Javascript, and using [`fast-check`](https://github.com/dubzzz/fast-check/blob/master/README.md) alongside [Jest](https://jestjs.io/) as our property-based testing framework.

The kata’s prompt is as follows:

> Complete the [`divisibleCount`] function that takes 3 numbers `x`, `y` and `k` (where `x ≤ y`), and returns the number of integers within the range `[x..y]` (both ends included) that are divisible by `k`.

## Writing Our Property Test

We could try to translate this prompt directly into a property test by generating three integers, `x`, `y`, and `k`, and verifying that the result of `divisibleCount(x, y, k)` matches our expected result, but we’d have to duplicate our implementation of `divisibleCount` to come up with that “expected result.” Who’s to say our test’s implementation wouldn’t be flawed?

We need a more obviously correct way of generating test cases.

Instead of generating three integers, `x`, `y`, and `k`, we’ll generate our starting point, `x`, the number we’re testing for divisibility, `k`, and the number of divisible numbers we expect in our range, `n`:

```

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(), fc.nat(), (x, k, n) => {
      // TODO ...
    })
  );
});

```

Armed with `x`, `k`, and `n`, we can compute the end of our range, `y`:

```

let y = x + n * k;

```

Next, we’ll pass `x`, our newly commuted `y`, and `k` into `divisibleCount` and assert that the result matches our expected value of `n`:

```

return n === divisibleCount(x, y, k);

```

Our final property test looks like this:

```

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(), fc.nat(), (x, k, n) => {
      let y = x + n * k;
      return n === divisibleCount(x, y, k);
    })
  );
});

```

Beautiful.

## Our First Solution

Coming up with a solution to this problem is fairly straight-forward:

```

const divisibleCount = (x, y, k) => {
  return _.chain(y - x)
    .range()
    .map(n => x + n)
    .reject(n => n % k)
    .size()
    .value();
};

```

We generate an array of integers from `x` to `y`, reject those that aren’t divisible by `k`, and return the size of the resulting array.

Unfortunately, this simple solution doesn’t work as expected. Our property test reports a failing counterexample of `[0, 0, 1]` values for `x`, `k`, and `n`:

```

$ jest
 FAIL ./index.test.js
  ✕ it works (10ms)
  
  ● it works
  
    Property failed after 1 tests
    { seed: 1427202042, path: "0:0:0:1:0:0:0", endOnFailure: true }
    Counterexample: [0,0,1]
    Shrunk 6 time(s)
    Got error: Property failed by returning false

```

Looking at our solution, this makes sense. The result of `n % 0` is undefined. Unfortunately, the kata doesn’t specify what the behavior of our solution should be when `k` equals `0`, so we’re left to figure that out ourselves.

Let’s just set up a precondition in our test that `k` should never equal `0`:

```

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(), fc.nat(), (x, k, n) => {
      fc.pre(k !== 0);
      let y = x + n * k;
      return n === divisibleCount(x, y, k);
    })
  );
});

```

Great!

Unfortunately, there’s another problem. Without putting an upper bound on the size of `n * k`, our solution will generate potentially massive arrays. This will quickly eat through the memory allocated to our process and result in a crash.

Let’s add some upper and lower bounds to our generated `k` and `n` values:

```

test("it works", () => {
  fc.assert(
    fc.property(fc.integer(), fc.integer(-100, 100), fc.nat(100), (x, k, n) => {
      fc.pre(k !== 0);
      let y = x + n * k;
      return n === divisibleCount(x, y, k);
    })
  );
});

```

Perfect. Our starting integer, `x`, can be any positive or negative integer, but our generated values of `k` are clamped between `-100` and `100`, and `n` ranges from `0` to `100`. These values should be large enough to thoroughly test our solution, and small enough to prevent memory issues from arising.

## Our Second Solution

In hindsight, our solution seems to be making inefficient use of both time and memory. If we consider the fact that our property test is computing `y` in terms of `x`, `n`, and `k`, it stands to reason that we should be able to compute `n`, our desired result, in terms of `x`, `y`, and `k`. If we can manage this, our solution will run in both constant time and constant space.

Let’s use some algebra and work our way backwards from calculating `y` to calculating `n`. If `y = x + n * k`, that means that `y - x = n * k`. Dividing by `k` gives us our equation for computing `n`: `n = (y - x) / k`.

Let’s replace our original `divisibleCount` solution with this equation:

```

const divisibleCount = (x, y, k) => (y - x) / k;

```

And rerun our test suite:

```

$ jest
 PASS ./index.test.js
  ✓ it works (8ms)
  
  Test Suites: 1 passed, 1 total
  Tests: 1 passed, 1 total

```

Wonderful!