CODEWITHSUNDEEP
javascript
jsjourney
jsjourney

Reputation: 11

Struggling with this js Codewars challenge

I am learning js and struggling with a problem I encountered on Codewars.

I need to calculate how many numbers containing only binary digits exist between 1 and a random number n. For example, if n is 20, there are 3 such numbers: 1, 10, 11;

I have written a solution that works on codepen but Codewars is telling me it is too inefficient to be accepted. I can't think of anything else I can do to optimize it. Thank you in advance for your help!

function incompleteVirus(n) {
  let countInMemory = 0;
  let isBinary = true;

  // Loop through all numbers below and including n
  for (let i = 1; i <= n; i++) { 

    let strCurrNum = String(i); 

    // Iterate through all digits in the current number
    for (const digit of strCurrNum) {
  
      let numDigit = Number(digit);
 
      // Check if each digit is binary; if not, exit loop
      if (numDigit > 1) {
        isBinary = false;
        break;
      } else {
        isBinary = true;
      }
    }

    // Update memory count
    if (isBinary) {
      countInMemory += 1;
    }
  } 
  return countInMemory
}

EDIT: I am linking the kata here if anyone is interested.

Upvotes: 1

Views: 383

Answers (2)

Seblor
Seblor

Reputation: 7146

That was an interesting kata to do, and I had some fun solving it.

I highly suggest you keep trying to solve it by yourself before reading the rest of my answer.

My approach was to check some examples and analyze the digits, rather than the whole numbers.

For example:

  • "10" => "10"
  • "27" => "11"
  • "101" => "101"
  • "102" => "101"
  • "121" => "111"
  • "1095" => "1011"

So here's what I understood from that pattern :

When a digit is higher than 1, replace all the digits on the left with 1s.
Otherwise (if the first digit is 0 or 1) replace any digit that is neither 0 or 1 to 1

So I started building a regular expression.

For the first case, I would need a positive lookbehind : (?<=[2-9].*)\d.
The second case is a simple [^01]

And since for both case, the digits need to be replaced by 1s, only a single replace is needed.

The resulting instruction, including the conversion to decimal, is:

parseInt(n.replace(/(?<=[2-9].*)\d|[^01]/g, 1), 2)

Upvotes: 2

Rodrigo Rodrigues
Rodrigo Rodrigues

Reputation: 8576

@Seblor's answer is the most straight-forward.

But in case you are curious about a solution without regex, here is one option with a more traditional foreach loop:

function bins(n) {
  let exx = false
  let acc = 0
  n.toString().split('').forEach((d, i, arr) => {
    // exx will be true from the moment any digit exceeds 1
    exx ||= d > 1  
    // if the current digit is positive, acc will add up a power of two
    acc += (exx || ~~d) && (2 ** (arr.length - i - 1))
  })
  return acc
}

console.log(bins(1112))

Upvotes: 0

Related Questions