Prime Number of Set Bits in Binary Representation

Challenge Points: 10

Level: Easy

You are given two integers left and right.
For every integer within this range (inclusive), convert it into its binary form and count how many 1 bits it contains.

A number is considered valid if the total number of 1s in its binary representation is a prime number.
(Prime numbers are greater than 1 and divisible only by 1 and themselves.)

Your task is to count how many values in the range [left, right] satisfy this condition and return that count.

Example 1:

Input: left = 5, right = 9

Output: 3

Explanation:

Binary forms: 5 → 101 (2 ones → prime) 6 → 110 (2 ones → prime) 7 → 111 (3 ones → prime) 8 → 1000 (1 one → not prime) 9 → 1001 (2 ones → prime) Valid numbers = 3.

Example 2:

Input: left = 12, right = 18

Output: 4

Explanation:

Binary ones count: 12 → 1100 (2 → prime) 13 → 1101 (3 → prime) 14 → 1110 (3 → prime) 15 → 1111 (4 → not prime) 16 → 10000 (1 → not prime) 17 → 10001 (2 → prime) 18 → 10010 (2 → prime) Valid count = 4.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result