This article is participating in Python Theme Month. See the link to the event for more details

describe

Given two integers left and right, find the count of numbers in the range [left, right] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: left = 6, right = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)
Copy the code

Example 2:

Input: left = 10, right = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
Copy the code

Note:

left, right will be integers left <= right in the range [1, 10^6].
right - left will be at most 10000.
Copy the code

parsing

The binary representation of a number in the range [left, right] contains a number in which the number of 1 is prime. You define a function to determine whether the number is prime or not, and then iterate over the number of 1’s in the binary of [left, right], counting the number of elements that have 1’s as prime.

answer

class Solution(object):
    def countPrimeSetBits(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        def isPrime(n):
            if n==1:
                return False
            if n==2:
                return True
            for i in range(2,n):
                if n%i==0:
                    return False
            return True
        result = 0
        for i in range(left, right+1):
            c = bin(i).count('1')
            if isPrime(c):
                result += 1
        return result
        	      
		
Copy the code

The results

Runtime: 420 ms, The link for Prime Number of Set Bits in Binary Representation is in the linked list. Submissions for Prime Number of Set Bits in Binary RepresentationCopy the code

parsing

We can also find some tips from the problem, because the maximum input is 10^6, and the closest number that satisfies the problem is 983,039, which contains 19 1’s. All we need to do is initialize a variable p that records all the primes with 1 in binary in the range 10^6, and then iterate through all the digits in [left, right] to see if the string containing 1 in binary in each element occurs in p. If it appears to satisfy the problem, the counter result is added by one. After the end of the traversal, the result obtained is the result.

answer

class Solution(object):
    def countPrimeSetBits(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: int
        """
        p = {2, 3, 5, 7, 11, 13, 17, 19}
        result = 0
        for i in range(left, right+1):
            if bin(i).count("1") in p:
                result += 1
        return result
Copy the code

The results

Runtime: 144 ms, The link for Prime Number of Set Bits in Binary Representation is in the linked list. Submissions for Prime Number of Set Bits in Binary RepresentationCopy the code

Link: leetcode.com/problems/pr…

Your support is my greatest motivation