ค้นหาผลรวมที่อาร์เรย์สามารถแบ่งออกเป็นอาร์เรย์ย่อยของผลรวมที่เท่ากันในPython

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม A; เราต้องหาค่าทั้งหมดของ sum เพื่อที่ค่า sum[i] อาร์เรย์สามารถแบ่งออกเป็นอาร์เรย์ย่อยของ sum sum[i] หากเราไม่สามารถแบ่งอาร์เรย์ออกเป็นอาร์เรย์ย่อยของผลรวมที่เท่ากันได้ ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น A =[2, 4, 2, 2, 2, 4, 2, 6] เอาต์พุตจะเป็น [6,8,12] เนื่องจากอาร์เรย์สามารถแบ่งออกเป็นอาร์เรย์ย่อยของ ผลรวม 6, 8 และ 12 เหล่านี้มีดังนี้:[{2, 4}, {2, 2, 2}, {4, 2}, {6}] [{2, 4, 2}, {2, 2 , 4},{2, 6}] [{2, 4, 2, 2, 2},{4, 2, 6

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

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

• table :=อาร์เรย์ขนาด n และเติม 0

• ตาราง[0] :=a[0]

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

  • table[i] :=a[i] + table[i - 1]

• S :=ตาราง[n - 1]

• my_map :=แผนที่ใหม่

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

  • my_map[table[i]] :=1

• ตอบ :=ชุดใหม่

• สำหรับฉันอยู่ในช่วง 1 ถึงส่วนจำนวนเต็มของ (รากที่สองของ (S)) + 1 ทำ

  • ถ้า S mod i เท่ากับ 0 แล้ว

    • is_present :=จริง

    • part_1 :=ผม

    • part_2 :=ผลหารของ S / i

    • สำหรับ j ในช่วง part_1 ถึง S + 1 อัปเดตในแต่ละขั้นตอนทีละ part_1 ทำ

      • ถ้า j ไม่อยู่ใน my_map แล้ว

        • is_present :=เท็จ

        • ออกจากวง

    • ถ้า is_present เป็นจริงและ part_1 ไม่เหมือนกับ S แล้ว

      • เพิ่ม (part_1) ของคำตอบ

    • is_present :=จริง

    • สำหรับ j ในช่วงเชาวน์ของ (S / i) ถึง S + 1 อัปเดตในแต่ละขั้นตอนโดย S // i ทำ

      • ถ้า j ไม่อยู่ใน my_map แล้ว

        • is_present :=เท็จ;

        • ออกจากวง

    • ถ้า is_present และ part_2 ไม่เหมือนกับ S แล้ว

      • เพิ่ม (part_2) ของคำตอบ

• ถ้าขนาดของคำตอบเท่ากับ 0 แล้ว

  • กลับ -1

• ส่งคืนคำตอบ

ตัวอย่าง

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

from math import sqrt
def find_sum(a) :
   n = len(a)
   table = [0] * n
   table[0] = a[0]
   for i in range(1, n) :
      table[i] = a[i] + table[i - 1]
   S = table[n - 1]
   my_map = {}
   for i in range(n) :
      my_map[table[i]] = 1
   answer = set()
   for i in range(1, int(sqrt(S)) + 1) :
      if (S % i == 0) :
         is_present = True;
         part_1 = i
         part_2 = S // i
         for j in range(part_1 , S + 1, part_1) :
            if j not in my_map :
               is_present = False
               break
         if (is_present and part_1 != S) :
            answer.add(part_1)
         is_present = True
         for j in range(S // i , S + 1 , S // i) :
            if j not in my_map:
               is_present = False;
               break
         if (is_present and part_2 != S) :
            answer.add(part_2)
   if(len(answer) == 0) :
      return -1
   return answer
a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))

อินพุต

[2, 4, 2, 2, 2, 4, 2, 6]

ผลลัพธ์

{8, 12, 6}