สมมติว่าเรามีจำนวนเต็ม L และ R สองตัว เราต้องหาจำนวนตัวเลขในช่วง [L, R] (รวม) ที่มีจำนวนเฉพาะของเซตบิตในรูปแบบไบนารี
ดังนั้น ถ้าอินพุตเป็น L =6 และ R =10 ผลลัพธ์จะเป็น 4 เนื่องจากมี 4 ตัวเลข 6(110),7(111),9(1001),10(1010) ทั้งหมดมีเฉพาะ จำนวนบิตที่ตั้งไว้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- นับ :=0
- สำหรับ j ในช่วง L ถึง R ให้ทำ
- ถ้ากำหนดจำนวนบิตของ j อยู่ใน [2,3,5,7,11,13,17,19] แล้ว
- นับ :=นับ + 1
- จำนวนคืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
คลาสโซลูชัน:def countPrimeSetBits(self, L, R):def popcount(i):return bin(i)[2:].count('1') count =0 for j in range(L,R+ 1):ถ้า popcount(j) ใน [2,3,5,7,11,13,17,19]:count +=1 return countob =Solution()print(ob.countPrimeSetBits(6,10)) อินพุต
6,10
ผลลัพธ์
4
