• 注册
    • 今日签到
    • 连续签到

    暂没有数据

    暂没有数据

    • 查看作者
    • 领扣:1324. Count Primes

      1046. Prime Number of Set Bits in Binary Representation

      中文English

      Given two integers L and R, find the count of numbers in the range [L, R] (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, 21written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

      Example

      Example 1:

      Input: L = 6, R = 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)

      Example 2:

      Input: L = 10, R = 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)

      Notice

      1.LR will be integers L <= R in the range [1, 10^6].
      2.R - L will be at most 10000

      class Solution:
          """
          @param L: an integer
          @param R: an integer
          @return: the count of numbers in the range [L, R] having a prime number of set bits in their binary representation
          """
          def countPrimeSetBits(self, L, R):
              # Write your code here
              result =0
              primearr = {2,3,5,7,11,13,17,19}
              for number in range(L,R+1):
                  if bin(number).count('1') in primearr:
                      result=result+1 
              return result

      The most L and R can go is 10000, which log(10000)/log(2) is 19 something.

      The set should be a {2,3,7,11,13,17,19}

      Then count for binary digits, whenever a number has a prime number of '1'. 

      Add one to result, later just return it. 

      Time complexity should be O(N), which N is R-L.

      Space complexity is O(1)

      纽约州·纽约
    • 0
    • 0
    • 0
    • 205