Skip to content

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..

What is binary gap?

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.

My solution

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));
Clone this wiki locally