Сложность: hard
Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.
Пример:
Input: left = 10, right = 15
Output: 5
👨💻 Алгоритм:
1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.
2⃣Создайте функцию для проверки, является ли число простым.
3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.
😎 Решение:
class Solution {
public:
int countPrimeSetBits(int left, int right) {
int count = 0;
for (int num = left; num <= right; num++) {
if (isPrime(__builtin_popcount(num))) {
count++;
}
}
return count;
}
private:
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
};Ставь 👍 и забирай 📚 Базу знаний