पायथन में सूची के सभी जोड़ों के संयोजन का योग निकालने का प्रोग्राम

संख्याओं की एक सूची nums दी गई है। हमें सूची में प्रत्येक जोड़ी के संयोजन (concatenation) का योग निकालना है। यहां जोड़ी (i, j) और (j, i) को अलग-अलग माना जाता है।

उदाहरण

इनपुट: nums = [5, 3]

संयोजन:

5 + 5 = 55
5 + 3 = 53
3 + 5 = 35
3 + 3 = 33

योग = 55 + 53 + 35 + 33 = 176

एल्गोरिदम

एक मेमोइज़ेशन डिक्शनरी memo बनाएं ताकि प्रत्येक अद्वितीय संख्या के लिए संयोजन योग कैश किया जा सके।
सूची के सभी तत्वों का योग total_sum में संग्रहीत करें (0 के विशेष मामले के लिए)।
प्रत्येक तत्व num के लिए:

यदि num == 0, तो total_sum जोड़ें (क्योंकि 0 के साथ संयोजन केवल दूसरा नंबर देता है)।
अन्यथा, यदि num मेमो में है, तो कैश्ड मान जोड़ें।
अन्यथा, सभी तत्वों के साथ num के संयोजन का योग निकालें, मेमो में स्टोर करें, और कुल में जोड़ें।

कुल योग वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, nums):
        memo = {}
        total_sum = sum(nums)
        n = len(nums)
        ans = 0
        
        for num in nums:
            if num == 0:
                ans += total_sum
            else:
                if num in memo:
                    ans += memo[num]
                else:
                    concat_sum = 0
                    for other in nums:
                        concat_sum += int(str(num) + str(other))
                    memo[num] = concat_sum
                    ans += concat_sum
        return ans

# परीक्षण
ob = Solution()
nums = [5, 3]
print(ob.solve(nums))  # आउटपुट: 176

अनुकूलित दृष्टिकोण (गणितीय)

संयोजन a concat b को a * 10^len(b) + b के रूप में लिखा जा सकता है। इसलिए कुल योग:

sum_{i,j} (nums[i] * 10^len(nums[j]) + nums[j])
= sum_i nums[i] * sum_j 10^len(nums[j]) + n * sum_j nums[j]

यह O(n) समय में गणना योग्य है।

समय जटिलता

दिए गए कार्यान्वयन: O(n² × d) जहां d औसत अंक संख्या है।
अनुकूलित: O(n × d)।