Skip to content

Instantly share code, notes, and snippets.

@clarketm
Last active October 12, 2022 12:13
Show Gist options
  • Save clarketm/2d1f83a1f117d4d36cf24a05712a857e to your computer and use it in GitHub Desktop.
Save clarketm/2d1f83a1f117d4d36cf24a05712a857e to your computer and use it in GitHub Desktop.
Largest Binary Gap (JavaScript)
function largestBinaryGap(num) {
var bin = Math.abs(num).toString(2),
finalMax = 0,
currentMax;
for (var i = 0; i < bin.length; i++) {
currentMax = 0;
while (bin[i] === "0") {
++currentMax && ++i;
}
finalMax = Math.max(finalMax, currentMax);
}
return finalMax;
}
console.log(largestBinaryGap(1)); // 1 //=> 0
console.log(largestBinaryGap(5)); // 101 //=> 1
console.log(largestBinaryGap(6)); // 110 //=> 1
console.log(largestBinaryGap(19)); // 10011 //=> 2
console.log(largestBinaryGap(1041)); // 10000010001 //=> 5
console.log(largestBinaryGap(6291457)); // 11000000000000000000001 //=> 20
console.log(largestBinaryGap(1376796946)); // 1010010000100000100000100010010 //=> 5
console.log(largestBinaryGap(1610612737)); // 1100000000000000000000000000001 //=> 28
@aaely
Copy link

aaely commented Dec 29, 2020

I did it like this

`function solution(N) {
const binary = N.toString(2)
let finalMax = 0, currentMax = 0

for(let i = 0; i < binary.length; i++) {
if(binary[i] == 1) {
i++
while(binary[i] == 0 && i < binary.length) {
currentMax++
i++
}
if (i == binary.length && binary[i] != 1) {
currentMax = 0
}
if(finalMax < currentMax) {
finalMax = currentMax
currentMax = 0
}
i--
}
currentMax = 0
}
return finalMax
}`

@Deyems
Copy link

Deyems commented Mar 12, 2021

I actually used this approach. How more ugly could it be? lol
function solution(N){
return Math.max(...countZeroesLengthInArray(splitNum(ignoreZeroesAfterLastOne(changeToBin(N)))))
}

const changeToBin = (num) => {
const toChange = num;
return toChange.toString(2);
}

const ignoreZeroesAfterLastOne = (numInString) => {
return numInString.slice(0, numInString.lastIndexOf("1") + 1);
}

const splitNum = (num) => {
return num.split("1");
}

const countZeroesLengthInArray = (arr) => {
return arr.map((curr) => {
return curr.length;
},0);
}

@Uzlopak
Copy link

Uzlopak commented Jun 27, 2021

I never saw so many solutions, which are kind of missing the point. Well actually the solution to transform to a "binary" string and splitting is actually funny, but I think most of you are just writing garbage.

The point of the task is to write the most efficient way to calculate the binary gap. This means to use less memory (=> use as less variables as possible), use less branching and use less calculations as possible.

My Solution:

function solution(N) {

    let start = null;
    let max = 0;

    for (let pos = 31; pos >= 0; pos--) {
        if ((N >> pos & 1) === 1) {
            if (start === null) {
                start = pos;
            } else {
                max = max < (start - pos) ? start - pos - 1 : max;
                start = pos;
            }
        }
    }

    return max;
}

Or even less by doing less subtractions:

function solution(N) {

    let start = null;
    let max = 1;

    for (let pos = 31; pos >= 0; pos--) {
        if ((N >> pos & 1) === 1) {
            if (start === null) {
                start = pos;
            } else {
                max = max < (start - pos ) ? start - pos : max;
                start = pos;
            }
        }
    }

    return --max;
}

Further improvements could be e.g. to first ignore all 0 at the beginning with a while loop and set the start then go through the for loop avoiding the branching if (start === null).

But really guys... some should be ashamed...

@Selvio
Copy link

Selvio commented Jul 24, 2021

function solution(N) {
    const number = N.toString(2)
    let max = 0;
    let currentMax = 0;
    for (let index = 0; index < number.length; index++) {
      if (number[index] === "0") currentMax++
      if (number[index] === "1") {
        max = Math.max(currentMax, max)
        currentMax = 0
      }
    }
    return max
}

@yamankatby
Copy link

The easiest solution

function solution(N) {
  return N.toString(2)
    .split("1")
    .slice(1, -1)
    .reduce((a, b) => (a > b.length ? a : b.length), 0);
}

@thiagodesa26
Copy link

thiagodesa26 commented Feb 10, 2022

Simple solution with 100% score:

function solution(N) {
  let newN = N.toString(2);
  let max = current = 0;
  for (char of newN) {
    if (char == "1") {
      max = Math.max(current, max);
      current = 0;
    } else {
      current++;
    }
  }
  return max;
}

@elpheen
Copy link

elpheen commented Mar 9, 2022

 function solution(N) {
  return N.toString(2)
    .split("1")
    .slice(1, -1)
    .reduce((a, b) => (a > b.length ? a : b.length), 0);
}

This was the one that made the most sense to me and helped debug my own code, thank you so much!

@viallymboma
Copy link

viallymboma commented Aug 18, 2022

After reading all these solutions, I came up with something that beginners can really easily understand:

const highestBinaryGap = (n)  => {
    let binary_number = n.toString(2)
    splited_binary_number = binary_number.toString().split("1")
    let maxCharacterArray = []
    for (let i = 0; i < splited_binary_number.length; i++) {
        if (splited_binary_number[i] !== "") {
            let length = splited_binary_number[i].length
            maxCharacterArray.push(length)
        }
    }
    let theHigestOccurance = Math.max(...maxCharacterArray)
    return theHigestOccurance
}
// Usage
theHigestBinaryGap = highestBinaryGap(593)
console.log(theHigestBinaryGap)

@Maulik3110
Copy link

Maulik3110 commented Oct 12, 2022

This is my solution with very less code and no direct loops

  function solution(N) {
      const binnum = Number(N).toString(2);
      let str = binnum.split('1');
      const newarr = str.filter(function(item,index){
          if (item === ''){
          }else if (index === str.length -1) {
          }else {
              return item;
          }
      })
      return newarr.length > 0 ? newarr.sort()[newarr.length -1].length : 0;
  }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment