โปรแกรมค้นหาจำนวนลำดับที่ตรงตามเงื่อนไขผลรวมที่กำหนดโดยใช้Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนลำดับย่อยที่ไม่ว่างของ nums เพื่อให้ผลรวมขององค์ประกอบต่ำสุดและสูงสุดขององค์ประกอบนั้นน้อยกว่าหรือเท่ากับ k คำตอบอาจมีขนาดใหญ่มาก ให้ส่งคืน mod 10^9 + 7

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4,6,7,8] k =11 เอาต์พุตจะเป็น 4 เนื่องจากมีลำดับย่อยเช่น

• [4] ที่นี่ขั้นต่ำคือ 4 สูงสุดคือ 4 ดังนั้น 4+4 <=11

• [4,6] ที่นี่ขั้นต่ำคือ 4 สูงสุดคือ 6 ดังนั้น 4+6 <=11

• [4,6,7] ที่นี่ขั้นต่ำคือ 4 สูงสุดคือ 7 ดังนั้น 4+7 <=11

• [4,7] ที่นี่ขั้นต่ำคือ 4 สูงสุดคือ 7 ดังนั้น 4+7 <=11

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

• เรียงเลขรายการ

• ม :=10^9 + 7

• ซ้าย :=0

• ขวา :=ขนาดของตัวเลข - 1

• res :=0

• ขณะที่ซ้าย <=ขวา ทำ

  • ถ้า nums[left] + nums[right]> k แล้ว

    • ขวา :=ขวา - 1

  • มิฉะนั้น

    • num_inside :=ขวา - ซ้าย

    • res :=(res + (2^num_inside) mod m) mod m

    • ซ้าย :=ซ้าย + 1

• ผลตอบแทน

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

ตัวอย่าง

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