สมมติว่าเรามีอาร์เรย์ nums และค่า k เราต้องหาจำนวน subsequences ที่ไม่ว่าง ที่ผลรวมของค่าต่ำสุดและค่าสูงสุดใน subsequence นั้น ≤ k คำตอบอาจใหญ่มาก จึงต้อง modulo 109 + 7
เช่น ถ้าข้อมูลเข้าเป็น nums = [4,6,7,8] k = 11 ผลลัพธ์จะเป็น 4 เพราะมี subsequences ที่ตรงเงื่อนไข ได้แก่ [4], [4,6], [4,6,7], [4,7]
ขั้นตอนการแก้ปัญหา
- เรียงลำดับ nums จากน้อยไปมาก
- กำหนด m = 109 + 7
- left = 0, right = len(nums) - 1
- res = 0
- วนลูป while left ≤ right:
- ถ้า nums[left] + nums[right] > k: right -= 1 (ค่าสูงสุดใหญ่เกินไป ลดลง)
- มิฉะนั้น:
- num_inside = right - left (จำนวนอิลิเมนต์ระหว่าง left และ right ที่เลือกได้หรือไม่เลือกก็ได้)
- res = (res + pow(2, num_inside, m)) % m (ทุก subset ของอิลิเมนต์กลางจะสร้าง subsequence ที่ถูกต้องร่วมกับ nums[left] และ nums[right])
- left += 1
- คืนค่า res
ตัวอย่างโค้ด
def solve(nums, k):
nums.sort()
m = 10**9 + 7
left = 0
right = len(nums) - 1
res = 0
while left <= right:
if nums[left] + nums[right] > k:
right -= 1
else:
num_inside = right - left
res = (res + pow(2, num_inside, m)) % m
left += 1
return res
nums = [4,6,7,8]
k = 11
print(solve(nums, k))
ข้อมูลเข้า
[4,6,7,8], 11
ข้อมูลออก
4
