Например, дана задача
/**
* Count ones in a segment
* Given two numbers: 'left' and 'right' (1 <= 'left' <= 'right' <= 200000000000000) return sum of all '1' occurencies in binary representations of numbers between 'left' and 'right' (including both)
Example:
countOnes 4 7 should return 8, because:
4(dec) = 100(bin), which adds 1 to the result.
5(dec) = 101(bin), which adds 2 to the result.
6(dec) = 110(bin), which adds 2 to the result.
7(dec) = 111(bin), which adds 3 to the result.
So finally result equals 8.
WARNING: Segment may contain billion elements, to pass this kata, your solution cannot iterate through all numbers in the segment!
*/
Как эволюционировать от таких решений
function countOnes(left, right) {
let sum = 0
const CountBits = (n) => Number(n).toString(2).split('')
.reduce((acc, v) => v==='1' ? ++acc : acc, 0)
for(let n = left; n<=right; n++){
sum+=CountBits(n)
}
return sum
}
К вот таким
function countOnesSingle(n) {
let result = 0;
while (n > 0) {
let k = Math.floor(Math.log2(n));
result += Math.pow(2, k - 1) * k + 1;
n = n - Math.pow(2, k);
result += n;
}
return result;
}
function countOnes(left, right) {
return countOnesSingle(right) - countOnesSingle(left - 1);
}
Очевидно, что простым нарешиванием делу не помочь.
p.s.
Нужны именно такие задачи, на большие числа. С задачи по типу "проверить правильно ли решено судоку" или "поделить грядки по какому-то замысловатому алгоритму" или "просчитать шахматную комбинацию" проблем нет. Но когда в дело вступют большие числа начинается фигня...
Простой
Простой
