# How To Solve Binary Gap

## How To Solve Codility’s First Code Challenge With JavaScript

# Why Code Challenges

Over the last few years, I have gotten more and more companies asking myself to do code challenges, do projects, and/or prove in some way that I have the knowledge to carry out a contract.

There are a variety of different things you can do to demonstrate your skills, including certification, and more so lately, code challenges.

# Code Challenge Websites

I definitely recommend taking on the challenge yourself on the some of the following websites:

- https://www.hackerrank.com
- https://app.codility.com/programmers/
- and many more listed in this article
**The 10 Best Coding Challenge Websites For 2018**

# Problem

Our problem for the binary gap challenge is basically:

- Expect an integer between 1 and 2,147,483,647
- Convert that integer into its binary value
- Return the length of the largest sequence of zeros in between ones
- Return 0 if no zeros in between ones

Or in a simpler terms:

- N is integer = 1–2,147,483,647
- N converted Binary (9 = 1001, 529 = 1000010001)
- 10000010001 = 5
- 1111 = 0
- 1001 = 2

**Goal**

Write a function or functions that returns these values

**Covering Our Bases**

First thing we need to do is cover our the very basic requirements:

- is an integer
- between 1 and 2,147,483,647
- convert number to binary

## Making Sure It’s An Integer

After doing some extensive research, you’ll see that I landed on a solution to type check with a strict comparison:

`// our function `

function solution (N) {

// Tests if our value is an integer

if (N === parseInt(N, 10)) {

}

// default if it doesn't meet the requirements

return 0;

}

## Within Its Limits

Next we want to add to that if to make sure it’s in fact within the range of 1 to 2,147,483,647:

`// our function `

function solution (N) {

// Tests if our value is an integer

// Tests if N is within range

if (N === parseInt(N, 10) && N >= 1 && N <= 2147483647) {

}

// default if it doesn't meet the requirements

return 0;

}

## Converting To Binary

In the video, I used the unsigned right shift operator, but that might not be needed because we aren’t using any negative numbers:

`// our function `

function solution (N) {

// Tests if our value is an integer

// Tests if N is within range

if (N === parseInt(N, 10) && N >= 1 && N <= 2147483647) {

// Convert to binary

const Binary = N.toString(2);

}

// default if it doesn't meet the requirements

return 0;

}

# Understanding The Problem

Now that we have covered our basis let’s look at the problem. My thinking is that in order to find a gap, I first need to sequential find the first one (1) and then the next one (1). My goal is then to store all the different gap lengths and just get the largest number. In order to do that, I’ll need to convert this to an array to get the position of each character to better search and index its value.

## Step 1, Converting To Array:

let N = 9;

const Binary = N.toString(2); // "1001"

const BinaryArray = Binary.split(''); // ["1", "0", "0", "1"]// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // 0// if the index is -1 then there was no ones to be found, ex 0000

## Step 2, Finding The First One:

Now that we have an array, I want to find the first index of “1” that exists. If the result is greater than or equal to zero (0), then a one exists in the array. If negative one (-1) that means that no ones were found, ex “0000” = -1:

let N = 9;

const Binary = N.toString(2); // "1001"

const BinaryArray = Binary.split(''); // ["1", "0", "0", "1"]// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // 0 = Index of array

Step 2, Finding The Next One:

The next step is to find the next one (1) in the array. The issue is that if we gave it the same array, it would still return 0, because the first one is at index 0. So what we need to do is remove that value from the array, essentially creating a new array, and searching for the next one.

let N = 9;

const Binary = N.toString(2); // "1001"

const BinaryArray = Binary.split(''); // ["1", "0", "0", "1"]// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // 0 = Index of array// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1);

// ["0", "0", "1"]

From there, we just need to traverse the array again look for another one:

let N = 9;

const Binary = N.toString(2); // "1001"

const BinaryArray = Binary.split(''); // ["1", "0", "0", "1"]// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // 0 = Index of array// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1);

// ["0", "0", "1"]// finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // 2

Coincidentally, the index number (2) also corresponds to the number of zeros (0) that are in between the ones (1).

## Storing Lengths In An Array

We want to store this value (2) in another array called gaps to store all the gap lengths that exist in the binary value. In this case, there is only one gap, but in the case that there are more, we need to store those values and find the largest gap.

let N = 9;

const Binary = N.toString(2); // "1001"

const BinaryArray = Binary.split(''); // ["1", "0", "0", "1"]// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // 0 = Index of array// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1);

// ["0", "0", "1"]// finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // 2// where we store our gaps

const gaps = [];// adding 2 to our gaps array

gaps.push(secondOne); // [2]

## Getting The Largest Length

Next, with our set of gap lengths, we just need to get the largest one from the array and return that value:

let N = 9;

const Binary = N.toString(2); // "1001"

const BinaryArray = Binary.split(''); // ["1", "0", "0", "1"]// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // 0 = Index of array// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1);

// ["0", "0", "1"]// finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // 2// where we store our gaps

const gaps = [];// adding 2 to our gaps array

gaps.push(secondOne); // [2]// getting largest value in array

return Math.max.apply(Math, gaps); // 2

And voila, we’ve solve the problem. Well, we solve the problem for the value of 9, but what about larger numbers like 529?

# Why Recursive Function

For larger numbers, we need to continuously split up our array and continually search through smaller and smaller arrays to find more gaps.

This is where recursion comes into to play, because we can write a single function that will take a chunk of an array, find the first one, cut it up, and pass the smaller array into itself again, until we find the next and then the next, all the way until there are no more ones.

## Refactoring For Recursion

To do this we need to take some of our code and put it in a separate function:

// NEW recursive function

function getGaps () {

// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // where we store our gaps

const gaps = []; // adding 2 to our gaps array

gaps.push(secondOne); // getting largest value in array

return Math.max.apply(Math, gaps); // 2

}// our function

function solution (N) {

// Tests if our value is an integer

// Tests if N is within range

if (N === parseInt(N, 10) && N >= 1 && N <= 2147483647) {

// Convert to binary

const Binary = N.toString(2).split('');

}

// default if it doesn't meet the requirements

return 0;

}

We can assume that in our recursive function, we need the binary array, and the gaps array to be passed along as more gap lengths are added to it, so we’ll refactor our code:

// NEW recursive function

function getGaps (BinaryArray, gaps) {

// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); // new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // where we store our gaps

const gaps = []; // adding 2 to our gaps array

gaps.push(secondOne); // getting largest value in array

return Math.max.apply(Math, gaps); // 2

}// our function

function solution (N) {

// Tests if our value is an integer

// Tests if N is within range

if (N === parseInt(N, 10) && N >= 1 && N <= 2147483647) {

// Convert to binary

const Binary = N.toString(2).split('');

// calling our recursive function with initial empty gaps

return getGaps(Binary, []);

}

// default if it doesn't meet the requirements

return 0;

}

## Factoring For No Ones

We need to refactor our code to account for no ones at all, otherwise we’ll return the number of gaps we found, which would initially be 0.

// NEW recursive function

function getGaps (BinaryArray, gaps) {

// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); if (firstOne > -1) {

// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // adding 2 to our gaps array

gaps.push(secondOne);

}

// if gaps array length is empty return 0

// otherwise return largest value in array

return (gaps.length > 0) ? Math.max.apply(Math, gaps) : 0;

}

## Accounting For No Zeros In Between

Next we need to account for new zeros in between the next one (1) that we find in array and make sure not to save that our gaps array. Example 110001, would return 0 for the first one, split it up to 10001, and return 0 for the second 1. This is what we are accounting for:

// NEW recursive function

function getGaps (BinaryArray, gaps) {

// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); if (firstOne > -1) {

// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // accounting for no zeros

if (secondOne > 0) {

// adding 2 to our gaps array

gaps.push(secondOne);

}

}

// if gaps array length is empty return 0

// otherwise return largest value in array

return (gaps.length > 0) ? Math.max.apply(Math, gaps) : 0;

}

## Continuing Our Recursion

Next we’ll need to pass the new array minus the second instance of one we did or did not find and continue passing our gaps array along to keep track of everything.

// NEW recursive function

function getGaps (BinaryArray, gaps) {

// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); if (firstOne > -1) {

// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // accounting for no zeros

if (secondOne > 0) {

// adding 2 to our gaps array

gaps.push(secondOne);

}

// Pass array minus second one and gaps array

return getGaps(NewBinaryArray.slice(secondOne +1), gaps);

}

// if gaps array length is empty return 0

// otherwise return largest value in array

return (gaps.length > 0) ? Math.max.apply(Math, gaps) : 0;

}

# Solution

Putting it all together, here is the entire code:

// NEW recursive function

function getGaps (BinaryArray, gaps) {

// finding the first one via its index

const firstOne = BinaryArray.indexOf("1"); if (firstOne > -1) {

// new array created taking a slice of original array

// from the index of the firstOne + 1 index

let NewBinaryArray = BinaryArray.slice(firstOne + 1); // finding second one via its index in new array slice

const secondOne = NewBinaryArray.indexOf("1"); // accounting for no zeros

if (secondOne > 0) {

// adding 2 to our gaps array

gaps.push(secondOne);

}

// Pass array minus second one and gaps array

return getGaps(NewBinaryArray.slice(secondOne +1), gaps);

}

// if gaps array length is empty return 0

// otherwise return largest value in array

return (gaps.length > 0) ? Math.max.apply(Math, gaps) : 0;

}// our function

function solution (N) {

// Tests if our value is an integer

// Tests if N is within range

if (N === parseInt(N, 10) && N >= 1 && N <= 2147483647) {

// Convert to binary

const Binary = N.toString(2).split('');

// calling our recursive function with initial empty gaps

return getGaps(Binary, []);

}

// default if it doesn't meet the requirements

return 0;

}

# Test Cases

Last step is to make sure that our code is running correctly and manually tests some outcomes:

// Scenarios:

// N = 9 (1001), Expected = 2

// N = 529 = (1000010001), Expected = 4

// N = 51272 (1100100001001000), Expected = 4

// N = 15 (1111), Expected = 0

// N = 53 (110101), Expected = 1

// N = 2147483647 (1111111111111111111111111111111), Expected = 0

// N = 2147483648 (10000000000000000000000000000000), Expected = 0

// N = 0 (0), Expected = 0

// N = -1 (null), Expected = 0

// N = "A" (null), Expected = 0

// N = null (null), Expected = 0

// N = [blank] (null), Expected = 0solution(9); // 2 ✅

solution(529); // 4 ✅

solution(51272); // 4 ✅

solution(15); // 0 ✅

solution(53); // 1 ✅

solution(2147483647); // 0 ✅

solution(2147483648); // 0 ✅

solution(0); // 0 ✅

solution(-1); // 0 ✅

solution("A"); // 0 ✅

solution(null); // 0 ✅

solution(); // 0 ✅

And there we have it. Our code passed our scenarios, handles the range and requirements, and ultimately solves the challenge.

**Feedback**

If you have any tips or recommendations on how this can be solved better, I would love to hear how, the why, and welcome any feedback.

If you got value from this, please give this article some applause and share it on twitter or other social media platforms. Thanks again for reading.

Please share it on twitter 🐦 or other social media platforms. Thanks again for reading. 🙏

Please also follow me on **twitter**: @codingwithmanny and **instagram** at @codingwithmanny.