Js Interview Series 5 должен знать бинарные задачи

Сегодня в нашей серии подготовки к Js Interview мы решим 5 обязательных двоичных задач из leetcode.

Задача: Сумма двух целых чисел

Решение:

var getSum = function (a,b) {
  if(b == 0) return a;
  return getSum(a^b,(a&b)<<1);
}

// a^b is xor operation 
// a&b << 1 is for carry calculation 
// Recursive call until we get no carry

Задача: Число 1 бит

Решение:

const numberOfOneBits = n => {
   let a = n.toString(2);
   let count = 0;
   for(let i = 0 ; i <a.length ; i++){
      if(a[i] == 1) count++;
    }
  return count;
}

Задача: Подсчет битов

Решение:

const numberOfOneBits = n => {
  var a = n.toString(2);
  let count = 0;
  for(let i = 0 ; i <a.length ; i++){
      if(a[i] == 1) count++;
   }
  return count;
}

const countingBits = n => {
  let out = [];
  for(let i = 0 ; i <= n ; i++){
    out.push(numberOfOneBits(i));
  }
  return out; 
}

Проблема: Недостающий номер

Решение 1:

const missingNumber = arr =>{
  arr.sort((a,b) => a-b);
  for(let i =0; i < arr.length ;i++){
    if(i !== arr[i]) return i;
  }
  return arr.length;
}

Решение 2:

const missingNumber = arr => {
  let sum = arr.reduce((a,b) => a+b)
  return arr.length * (arr.length +1)/2 - sum;
}

//using formula sum of n natural numbers =>n*(n+1)/2
// calculating sum of all the numbers in array using reduce method
// difference between two sums is the final answer or the missing number.

Задача: Обратные биты

Решение:

var reverseBits = function(n) {
    return parseInt(n.toString(2).padStart(32, '0').split('').reverse().join(''), 2);
};

//padstart is to add 0's to the start to make it a 32 bit integer.
//post which its just split and covert to array to reverse the array and join it back
//Then parseInt for the binary number.