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.
That was an interesting kata to do, and I had some fun solving it.
My approach was to check some examples and analyze the digits, rather than the whole numbers.
For example:
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)
@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))