How To Solve Binary Gap
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.
