Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

👨‍💻 Алгоритм:

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

function countPrimeSetBits($left, $right) {
    function countBits($x) {
        return substr_count(decbin($x), '1');
    }
    
    function isPrime($x) {
        if ($x < 2) return false;
        for ($i = 2; $i * $i <= $x; $i++) {
            if ($x % $i == 0) return false;
        }
        return true;
    }
    
    $count = 0;
    for ($num = $left; $num <= $right; $num++) {
        if (isPrime(countBits($num))) {
            $count++;
        }
    }
    return $count;
}

Ставь 👍 и забирай 📚 Базу знаний