पायथन में दिए गए ऐरे से अधिकतम nCr मान वाला युग्म खोजें

मान लीजिए हमारे पास n पूर्णांकों का एक ऐरे arr है। हमें ऐरे से arr[i] और arr[j] ढूंढने हैं जैसे कि arr[i]Carr[j] यथासंभव बड़ा हो। यदि एक से अधिक युग्म हैं, तो उनमें से कोई भी एक लौटाएं।

इसलिए, यदि इनपुट [4, 1, 2] है, तो आउटपुट 4 2 होगा क्योंकि 4C1 = 4, 4C2 = 6 और 2C1 = 2, इसलिए (4,2) ही एकमात्र इच्छित युग्म है।

समाधान दृष्टिकोण

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

• सूची v को सॉर्ट करें।
• N := v[n - 1] (सबसे बड़ा तत्व)।
• यदि N % 2 == 1 (विषम), तो:
  • first := N // 2
  • second := first + 1
  • left := -1, right := -1, temp := -1
  • i को 0 से n-1 तक के लिए:
    • यदि v[i] > first, तो temp := i और ब्रेक करें।
    • अन्यथा, difference := first - v[i]; यदि difference < res1, तो res1 := difference, left := v[i]
  • right := v[temp]
  • difference1 := first - left, difference2 := right - second
  • यदि difference1 < difference2, तो (N, left) प्रिंट करें।
  • अन्यथा, (N, right) प्रिंट करें।
• अन्यथा (सम):
  • max := N // 2
  • res := 3 * 10¹⁸, R := -1
  • i को 0 से n-2 तक के लिए:
    • difference := |v[i] - max|
    • यदि difference < res, तो res := difference, R := v[i]
  • (N, R) प्रिंट करें।

उदाहरण

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

def findMatrixPair(v, n):
    v.sort()
    N = v[n - 1]
    if N % 2 == 1:
        first = N // 2
        second = first + 1
        res1, res2 = 3 * (10 ** 18), 3 * (10 ** 18)
        left, right = -1, -1
        temp = -1
        for i in range(0, n):
            if v[i] > first:
                temp = i
                break
            else:
                difference = first - v[i]
                if difference < res1:
                    res1 = difference
                    left = v[i]
        right = v[temp]
        difference1 = first - left
        difference2 = right - second
        if difference1 < difference2:
            print(N, left)
        else:
            print(N, right)
    else:
        max_val = N // 2
        res = 3 * (10 ** 18)
        R = -1
        for i in range(0, n - 1):
            difference = abs(v[i] - max_val)
            if difference < res:
                res = difference
                R = v[i]
        print(N, R)

v = [4, 1, 2]
n = len(v)
findMatrixPair(v, n)

इनपुट

[4,1,2], 3

आउटपुट

4 2