Largest Binary Gap (JavaScript)

largestBinaryGap.js

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

Hi,

Its failing in this case
largestBinaryGap(6); // 110 expecting 0 but its gives 1

and every case where consecutive zeros are not surrounded by 1.

A minor correction in the code above.

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;
    }
    if (bin[i] === '1' ) finalMax = Math.max(finalMax, currentMax);
  }
  return finalMax;
}

i create another way

function solution(N) {
    // write your code in JavaScript (Node.js 8.9.4)
    const bin = Math.abs(N).toString("2")
    let finalMax = 0, currentMax=0
    
    for(i=0;i < bin.length; i++ ) {
        if(bin[i] == "0") {
            currentMax++
        }
        
        if(bin[i] == "1" && i != 0) {
            finalMax = Math.max(finalMax, currentMax)  
            currentMax = 0
        }
        
    }
    
    return parseInt(finalMax)
}

console.log(largestBinaryGap(6)); needs to be 0

function largestBinaryGap(N) {
    const bin = (N) => (N >>> 0).toString(2);
    const valuesMap = {};
    let key = null;
    
    for (let i = 0; i < bin.length; i++) {
        if (bin[i] === '1') {
            key = i+1;
            valuesMap[key] = 0
        } else {
            if (bin[i+1]) {
               valuesMap[key] = valuesMap[key] + 1
            } else {
              delete valuesMap[key];
            }
            
        }
    }
  
    const values = Object.values(valuesMap);

    return values.length ? Math.max.apply(null, values) : 0;
}

Hi. I got the same challenge online somewhere, and here is what came up with.

function largestBinaryGap(N){ 
  let maxGap = 0;
  let currentGap = 0;
  let binaryN = N.toString(2); //Convert number to binary string
  let len = binaryN.length; // Length of Binary string
  let posOne = binaryN.lastIndexOf('1'); // First occurrence of 1 from the right

 for(let i = posOne; i > 0; i--){
    
    if(binaryN.charAt(i) == '1'){
        currentGap = 0; // reset gap counter to zero
    }else{
        currentGap = currentGap + 1;
        //console.log(`Current count is ${currentGap}`);
        if(currentGap > maxGap){
            maxGap = currentGap;
        }
    }      
    
}
return maxGap;

}

Better version from me:

var str = "1000100000000";

var max = 0, temp = 0;
for(i = 0 ; i <= str.length; i++) {
  if(str[i] & 1 && !temp) temp = 1;
  temp += (str[i+1] === '0' && !!temp);
  if(str[i+1] & 1 && !!temp) {
    max = Math.max(temp - 1, max);
    temp = 0;
  }
}

console.log(max);

Hi,

Its failing in this case
largestBinaryGap(6); // 110 expecting 0 but its gives 1

and every case where consecutive zeros are not surrounded by 1.

Good catch. We need to accommodate negative integers in true binary, and Math.abs() doesn't allow for that. Instead of calling Math.abs(num).toString(2), use (num >>> 0).toString(2)

Here's a function broken out...

// zero-fill right shift
function shift2Bin(num) {
  if (Number.isInteger(num)) {
    return (num >>> 0).toString(2);
  }
}

function largestBinaryGap(num) {
  var bin = shift2Bin(num),
    finalMax = 0,
    currentMax;

  for (var i = 0; i < bin.length; i++) {
    currentMax = 0;
    while (bin[i] === '0') {
      ++currentMax && ++i;
    }
    if (bin[i] === '1') finalMax = Math.max(finalMax, currentMax);
  }
  return finalMax;
}

Hi,

Its failing in this case
largestBinaryGap(6); // 110 expecting 0 but its gives 1

and every case where consecutive zeros are not surrounded by 1.

console.log(largestBinaryGap(6)); needs to be 0

function largestBinaryGap(N) {
    const bin = (N) => (N >>> 0).toString(2);
    const valuesMap = {};
    let key = null;
    
    for (let i = 0; i < bin.length; i++) {
        if (bin[i] === '1') {
            key = i+1;
            valuesMap[key] = 0
        } else {
            if (bin[i+1]) {
               valuesMap[key] = valuesMap[key] + 1
            } else {
              delete valuesMap[key];
            }
            
        }
    }
  
    const values = Object.values(valuesMap);

    return values.length ? Math.max.apply(null, values) : 0;
}

This is the correct approach to binary conversion. Nice catch!

Math.abs() circumvents negative integer binary representation (for example, reflective compliment of 2's

instead of Math.abs(num).toString(2), use (num >>> 0).toString(2), or better yet (since this is most likely for a coding/algo assessment, break it out into a function and ensure the integer:

// zero-fill right shift
function shift2Bin(num) {
  if (Number.isInteger(num)) {
    return (num >>> 0).toString(2);
  }
}

a bit cheeky, but here's my solution for a positive value:

function solution(N) {
    return N
        .toString(2)
        .replace(/(^0+|0+$)/, '')
        .split('1')
        .reduce((carry, entry) => {
            return entry.length > carry ? entry.length : carry
        }, 0)
}

My Solution

function solution(N) {
    const bin = N.toString(2);
    const strArr = bin.split(1);
    let max = 0;
   // ignore first and last index in the array.
    for (let i = 1; i < (strArr.length - 1); i++) {
        if (strArr[i].length > max) {
            max = strArr[i].length;
        }
    }
    return max;
}

function mindTheGap(n) {
  const str = n.toString(2)
  const substr = str.substring(0, str.lastIndexOf('1'))
  const split = substr.split('1')  
  return split.sort().reverse()[0].length
}

Even better;

function solution(N) {
    const binary = N.toString(2)
    const splitedZeros = binary.substring(0, binary.lastIndexOf('1')).replace(/^1/, '').split('1');
    return Math.max(...(splitedZeros.map(el => el.length)))
}

Nice to read and understand:

function solution(N) {
    return N
      .toString(2)
      .replace(/[0]*$/, '')
      .split('1')
      .reduce((acc, a) =>
        a.length > acc ? a.length : acc
      , 0);
}

This is a very correct function that passed all test cases.

function solution(N) { // write your code in JavaScript (Node.js 8.9.4) let bin = (N >>> 0).toString(2); let binarr = bin.split('1'); let count_arr = []; for (let i = 0; i < binarr.length; i++) { if (i == 0 || i == binarr.length - 1) continue; else{ count_arr.push(binarr[i].length); } }; // console.log(count_arr); // console.log(Math.max( ...count_arr )); if (count_arr.length == 0){ return 0; }else{ return Math.max( ...count_arr ); } }

This is my example. Test Results Score 86% in Codility

function solution(N) {
    // write your code in JavaScript (Node.js 8.9.4)
    if(N.toString(2).match(/1[0]*1/)) {
        return N.toString(2).split("1").sort((x,y) => {return y.length-x.length})[0].length;
    } else return 0;
}

This is my example. Test Results Score 100% in Codility

solution = (N) => {
 var a = N.toString(2).split('');
 //console.log(a)
 var max = 0;
 var count = 0;
 for(var i = 0; i < a.length; i++) {
    //console.log(max, count)
      if (a[i] == 1 && a[i+1] == 0 || (count > 0 && a[i] == 0 && a[i+1] == 1)) {
         max = Math.max(max, count);
         count = 1;
      } else if (count > 0 && a[i] == 0 && a[i+1] == 0) {
         count++; 
      } 
 }
 return max;
}

//life is simple dont let any one give you a complex code to learn
//just read between the lines and understand the question

//given N
const given = N;
let noZeroes = false; // task is to loop to count zeroes before a 1 right?
const bin = N.toString(2) // needed
//console.log(bin)
let counter =0; // the counter
let jackPot = []; // yeah did it get me a 1
let binArr = bin.split("") // convert the bin to array so we can loop the hell out of it

const resetCounter = function(){counter =0 ; } // yeah i need to reset count to 0 when i hit a 1 so i can count for other 0's before the next 1

for(let i=0; i<binArr.length; i++){ // the looping hell master
  if(parseInt(binArr[i])==0){ // of course you get this point
      counter++
      noZeroes = false;
  }else if(binArr[i]==1 && counter>0){ // here we make sure that our count is > 0
      jackPot.push(counter) // hmmm
      resetCounter() // ahuh
      noZeroes = false; //woop me
      
  }  else{
      noZeroes==true // finally just incase we dont see a 1 again 
      
  }  
   
}


//console.log(jackPot)
if(jackPot.length>0){
    const max = Math.max( ...jackPot);
//  console.log(max)
  return parseInt(max) 
}
return 0

//gracias

}

I got 100% with this code.

function solution(N) {
    let binary = parseInt(N).toString(2);
    let remove_last_zero = binary.slice(0, binary.lastIndexOf("1") + 1);
    let split_1 = remove_last_zero.split("1");
    let remove_empty = split_1.filter(i => i != "");
    if (typeof remove_empty !== 'undefined' && remove_empty.length == 0) {
        return 0;
    }
    let zero_count = remove_empty.map(b => b.length);
    return Math.max.apply(null, zero_count);
}

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
}`

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);
}

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

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
}

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);
}

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;
}

 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!

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)

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;
  }