โปรแกรมนับชุดย่อยที่ไม่ว่างโดยที่ผลรวมขององค์ประกอบต่ำสุดและสูงสุดของชุดมีค่าน้อยกว่า k ใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนชุดย่อยที่ไม่ว่าง S ให้มีค่าต่ำสุดของ S + สูงสุดของ S <=k เราต้องจำไว้ว่าชุดย่อยเป็นชุดหลายชุด ดังนั้น อาจมีค่าที่ซ้ำกันในเซตย่อย เนื่องจากค่าเหล่านี้อ้างอิงถึงองค์ประกอบเฉพาะของรายการ ไม่ใช่ค่า

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 2, 5, 6], k =7 ผลลัพธ์จะเป็น 6 เนื่องจากเราสามารถสร้างเซตย่อยต่อไปนี้ได้ เช่น:[2], [2], [2, 2], [2, 5], [2, 5], [2, 2, 5].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=ขนาด A
• เรียงลำดับรายการ A
• ตอบ :=0
• j :=N - 1
• สำหรับผมในช่วง 0 ถึง N ให้ทำ
  • ในขณะที่ j และ A[i] + A[j]> K ทำ
    • j :=j - 1
  • ถ้าฉัน <=j และ A[i] + A[j] <=K แล้ว
    • ans :=ans + 2^(j - i)
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, A, K):
      N = len(A)
      A.sort()
      ans = 0
      j = N - 1
      for i in range(N):
         while j and A[i] + A[j] > K:
            j -= 1
            if i <= j and A[i] + A[j] <= K:
               ans += 1 << (j - i)
      return ans
ob = Solution()
nums = [2, 2, 5, 6]
k = 7 print(ob.solve(nums, k))

อินพุต

[2, 2, 5, 6]

ผลลัพธ์

6