चार सूचियों से टारगेट से कम योग बनाने वाले अद्वितीय चार इंडेक्स की संख्या ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास A, B, C और D चार संख्याओं की सूचियाँ हैं और एक और संख्या target है। हमें अलग-अलग अद्वितीय इंडेक्स i, j, k, l की संख्या ढूंढनी है जैसे कि A[i] + B[j] + C[k] + D[l] ≤ target।

उदाहरण के लिए, यदि इनपुट A = [3, 2] B = [5, 3] C = [1] D = [2, 3] target = 9 है, तो आउटपुट 3 होगा, क्योंकि हम निम्न संयोजन चुन सकते हैं: [3, 3, 1, 2] [3, 3, 1, 2] [2, 3, 1, 3]

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

temp_list := एक नई सूची
i को 0 से A के आकार तक के लिए, करें
- j को 0 से B के आकार तक के लिए, करें
  - (A[i] + B[j]) को temp_list के अंत में डालें
temp_list को क्रमबद्ध करें
ans := 0
i को 0 से C के आकार तक के लिए, करें
- j को 0 से D के आकार तक के लिए, करें
  - sum_cd := C[i] + D[j]
  - sum_ab := target - sum_cd
  - ans := ans + temp_list में उन तत्वों की संख्या जिनका योग <= sum_ab है
ans लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

from bisect import bisect_right
class Solution:
    def solve(self, A, B, C, D, target):
        temp_list = []
        for i in range(len(A)):
            for j in range(len(B)):
                temp_list.append(A[i] + B[j])
        temp_list.sort()
        ans = 0
        for i in range(len(C)):
            for j in range(len(D)):
                sum_cd = C[i] + D[j]
                sum_ab = target - sum_cd
                ans += bisect_right(temp_list, sum_ab)
        return ans

ob = Solution()
A = [3, 2]
B = [5, 3]
C = [1]
D = [2, 3]
target = 9
print(ob.solve(A, B, C, D, target))

इनपुट

[3, 2], [5, 3], [1], [2, 3], 9