package com.fishercoder.solutions;

/**
 * 762. Prime Number of Set Bits in Binary Representation
 *
 * 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, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

 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)

 Note:

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

public class _762 {
  public static class Solution1 {
    public int countPrimeSetBits(int L, int R) {
      int count = 0;
      for (int i = L; i <= R; i++) {
        if (hasPrimeNumberSetBits(i)) {
          count++;
        }
      }
      return count;
    }

    private boolean hasPrimeNumberSetBits(int num) {
      int k = getSetBits(num);
      if (k <= 1) {
        return false;
      }
      for (int i = 2; i * i <= k; i++) {
        if (k % i == 0) {
          return false;
        }
      }
      return true;
    }

    private int getSetBits(int n) {
      int bits = 0;
      while (n != 0) {
        bits++;
        n &= (n - 1);
      }
      return bits;
    }
  }
}

@@ -33,1019 +33,8 @@
 s;%0A%0A
-/**%0A * 762. Prime Number of Set Bits in Binary Representation%0A *%0A * Given two integers L and R, find the count of numbers in the range %5BL, R%5D (inclusive) having a prime number of set bits in their binary representation.%0A * (Recall that the number of set bits an integer has is the number of 1s present when written in binary.%0A * For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)%0A%0A Example 1:%0A%0A Input: L = 6, R = 10%0A Output: 4%0A%0A Explanation:%0A 6 -%3E 110 (2 set bits, 2 is prime)%0A 7 -%3E 111 (3 set bits, 3 is prime)%0A 9 -%3E 1001 (2 set bits , 2 is prime)%0A 10-%3E1010 (2 set bits , 2 is prime)%0A%0A Example 2:%0A%0A Input: L = 10, R = 15%0A Output: 5%0A%0A Explanation:%0A 10 -%3E 1010 (2 set bits, 2 is prime)%0A 11 -%3E 1011 (3 set bits, 3 is prime)%0A 12 -%3E 1100 (2 set bits, 2 is prime)%0A 13 -%3E 1101 (3 set bits, 3 is prime)%0A 14 -%3E 1110 (3 set bits, 3 is prime)%0A 15 -%3E 1111 (4 set bits, 4 is not prime)%0A%0A Note:%0A%0A L, R will be integers L %3C= R in the range %5B1, 10%5E6%5D.%0A R - L will be at most 10000.%0A */%0A%0A
 publ
@@ -49,16 +49,18 @@
  _762 %7B%0A
+  
   public
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     publ
@@ -134,24 +134,30 @@
 L, int R) %7B%0A
+      
       int co
@@ -161,24 +161,30 @@
  count = 0;%0A
+      
       for (i
@@ -212,24 +212,32 @@
 ) %7B%0A        
+   
+     
 if (hasPrime
@@ -252,24 +252,34 @@
 tBits(i)) %7B%0A
+          
           co
@@ -289,34 +289,54 @@
 ++;%0A        
+   
-%7D%0A
+     %7D%0A     
       
+ 
 %7D%0A
+      
       return
@@ -343,27 +343,35 @@
  count;%0A    
+  
+  
 %7D%0A%0A
+    
     private 
@@ -413,24 +413,30 @@
 um) %7B%0A      
+    
+  
 int k = getS
@@ -448,16 +448,22 @@
 s(num);%0A
+      
       if
@@ -474,32 +474,40 @@
 %3C= 1) %7B%0A        
+ 
+       
 return false;%0A  
@@ -506,26 +506,38 @@
 alse;%0A      
+   
-%7D%0A
+   %7D%0A      
       for (i
@@ -557,32 +557,40 @@
  i %3C= k; i++) %7B%0A
+        
         if (k %25 
@@ -595,24 +595,34 @@
 %25 i == 0) %7B%0A
+          
           re
@@ -645,24 +645,44 @@
     
+        %7D%0A            
 %7D%0A     
- %7D%0A
       
+ 
 retu
@@ -690,27 +690,35 @@
 n true;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     private 
@@ -737,24 +737,30 @@
 ts(int n) %7B%0A
+      
       int bi
@@ -773,16 +773,22 @@
 ;%0A      
+   
+   
 while (n
@@ -808,16 +808,24 @@
     
+       
+ 
 bits++;%0A
     
@@ -816,24 +816,32 @@
     bits++;%0A
+        
         n &=
@@ -852,26 +852,38 @@
 - 1);%0A      
-%7D%0A
+      %7D%0A      
       return
@@ -893,16 +893,22 @@
 ts;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 762