How to get binary gap count
daisho edited this page Jul 23, 2020
·
2 revisions
Find longest sequence of zeros in binary representation of an integer..
Binary gap is is any sequence of consecutive zeros that is surrounded by ones at both ends in the binary representations of N.
For example, number 9 has binary representation 1001 and contains a binary gap 00 which is length of 2. The number 529 is 1000010001 and contains two binary gaps: one of length 4 and one of length 3.
I know there must be better solutions, but this is what I came up with.
Note that bainary representation of decimal 40 is supposed to be 00101000
but JavaScript toString
method returns without prefixed zeros: 101000
.
function getLargestBinaryGapCount(v) {
// v === 40
if (typeof v === "number") {
// converts integer into binary
v = v.toString(2);
}
if (typeof v === "string") {
// converts string into an array: ["1", "0", "1", "0", "0", "0"]
v = v.split("");
console.log("Initial binary:", v);
}
// if the binary is for integer 0 (00000000) return 0
if (!v.includes("1")) return 0;
// if the binary starts with zeros, overwrite v without prefixed zeros
v = v.slice(v.indexOf("1"));
let found = false;
let count = 0;
const accum = [];
function recursive(arr) {
// if the array contains only zeros, end the recursion
if (arr.indexOf("1") <= -1) return accum;
if (arr[0] === "0") {
found = true;
count++;
if (arr.length >= 2) {
return recursive(arr.slice(1));
}
}
if (found && arr[0] === "1") {
accum.push(count);
count = 0;
found = false;
if (arr.length >= 2) {
return recursive(arr.slice(1));
}
}
if (!found && arr[0] === "1") {
count = 0;
accum.push(count);
if (arr.length >= 2) {
return recursive(arr.slice(1));
}
}
return accum;
}
const result = recursive(v).sort((a, b) => a - b);
return result[result.length - 1];
}
console.log("ANSWER:", getLargestBinaryGapCount(40));