CODEWITHSUNDEEP
javascriptarrayslargenumber
Liucia Liv
Liucia Liv

Reputation: 21

JavaScript loop is too slow

I'm working on a task on codewars and cannot understand how to make this function work faster for large numbers <= 200000000000000. The goal of the function is very simple - I just need to count all '1' occurrences in binary representations of numbers between 'left' and 'right' (including both).

function countOnes(left, right) {
var sum=0;
for (var i=left; i<=right; i++){
    var h=i.toString(2);
    var len=h.length;
    for (var j=0; j<len; j++){
        if (h[j]==1){sum++;}
    }
}
return sum;
}

Thanks in advance

Upvotes: 2

Views: 560

Answers (2)

Mister Jojo
Mister Jojo

Reputation: 22319

As Bitwise operators are limited to 32bits (see remarks) this solution push this limit to 2**53 -1 which is the value of JS Number.MAX_SAFE_INTEGER
see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER 

const p32 = 2**32

function countOnes_John_MJojo(left, right )
  {
  let sum = 0
  for (let V=left; V<=right; V++)
    {
    for (let N=V;N; N&=N-1) sum++
    for (let N=Math.trunc(V/p32);N; N&=N-1) sum++
    } 
  return sum
  }

/- history : -\
\--------------/

A little bit faster is using Bitwise operators:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

-> logical AND
-> Logical Right shift

function countOnesBin( left, right )
  {
  let sum = 0
  for (let N=left; N<=right; N++)
    {
    let Bin = N
    for(let x = N.toString(2).length;x--;)
      {
      if ( Bin & 1 ) sum++ 
      Bin = Bin >>1
      } 
    } 
  return sum
  }

as @CodeBling suggest this one could be better ! 

function countOnes_CodeBling  (left, right)
  {
  let sum = 0
  for (let N=left; N<=right; N++)
    {
    for(let Bin = N; Bin > 0; Bin = Bin >> 1)
      { if ( Bin & 1 ) sum++  } 
    } 
  return sum
  }

this one is the best! I did not know the possibility: Thanks to @John

function countOnes_John (left, right)
  {
  let sum = 0
  for (let V=left; V<=right; V++)
    {
    for (let N=V;N; N&=N-1) sum++
    } 
  return sum
  }

Upvotes: 1

Silvano Gonz&#225;lez
Silvano Gonz&#225;lez

Reputation: 391

You could avoid the second iteration using a split function and adding the amount of chunks minus one to your sum:

function countOnes(left, right) {
  var sum=0;
  for (var i=left; i<=right; i++){
    var h=i.toString(2);
    sum += h.split('1').length -1;
  }
  return sum;
}

It would be still slow, but a lot faster than your original code.

Upvotes: 0

Related Questions