ค้นหาลำดับย่อยที่ยาวที่สุดของอาร์เรย์ที่มี LCM ที่ K มากที่สุดใน Python

สมมติว่าเรามีอาร์เรย์ A ของตัวเลขที่แตกต่างกันจำนวน n ตัวและจำนวนเต็มบวก K ตัวอื่น เราต้องหาลำดับย่อยที่ยาวที่สุดในอาร์เรย์ที่มีตัวคูณร่วมน้อย (LCM) ที่มากที่สุด K จากนั้นจึงคืนค่า LCM และความยาวของค่าย่อย -ลำดับ ตามดัชนี (เริ่มจาก 0) ขององค์ประกอบของลำดับย่อยที่ได้รับ มิฉะนั้น ให้ส่งคืน -1

ดังนั้น หากอินพุตเป็น A =[3, 4, 5, 6], K =20 เอาต์พุตจะเป็น LCM =12, ความยาว =3, ดัชนี =[0,1,3]

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

• n :=ขนาดของ A

• my_dict :=แผนที่

• สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

  • my_dict[A[i]] :=my_dict[A[i]] + 1

• count :=อาร์เรย์ขนาด (k + 1) เติมด้วย 0

• สำหรับแต่ละคีย์ใน my_dict ให้ทำ

  • ถ้าคีย์ <=k แล้ว

    • ผม :=1

    • ในขณะที่คีย์ * i <=k ทำ

      • นับ[คีย์ * i] :=นับ[คีย์ * i] + my_dict[คีย์]

      • ผม :=ผม + 1

  • มิฉะนั้น

    • ออกจากวง

• lcm :=0, ขนาด :=0

• สำหรับฉันอยู่ในช่วง 1 ถึง k + 1 ทำ

  • ถ้านับ[i]> ขนาด แล้ว

    • ขนาด :=นับ[i]

    • lcm :=ผม

• ถ้า lcm เท่ากับ 0 แล้ว

  • กลับ -1

• มิฉะนั้น

  • แสดง lcm และขนาด

  • สำหรับผมอยู่ในช่วง 0 ถึง n ทำ

    • ถ้า lcm mod A[i] เหมือนกับ 0 แล้ว

      • จอแสดงผล

ตัวอย่าง

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

from collections import defaultdict
def get_seq(A,k):
   n = len(A)
   my_dict = defaultdict(lambda:0)
   for i in range(0, n):
      my_dict[A[i]] += 1
   count = [0] * (k + 1)
   for key in my_dict:
      if key <= k:
         i = 1
         while key * i <= k:
            count[key * i] += my_dict[key]
            i += 1
      else:
         break
   lcm = 0
   size = 0
   for i in range(1, k + 1):
      if count[i] > size:
         size = count[i]
         lcm = i
   if lcm == 0:
      print(-1)
   else:
      print("LCM = {0}, Length = {1}".format(lcm, size))
      print("Index values: ", end = "")
      for i in range(0, n):
         if lcm % A[i] == 0:
            print(i, end = " ")

k = 20
A = [3, 4, 5, 6]
get_seq(A,k)

อินพุต

[3, 4, 5, 6] , 20

ผลลัพธ์

LCM = 12, Length = 3 Index values: 0 1 3