पायथन में ऐरे के युग्मवार अंतर को जोड़कर खेल का विजेता खोजें

मान लीजिए हमारे पास धनात्मक पूर्णांकों का एक ऐरे A है, जिसके तत्व अद्वितीय हैं। अब, दो खिलाड़ी P और Q एक खेल खेल रहे हैं। प्रत्येक चाल में, कोई भी खिलाड़ी ऐरे से दो संख्याएं a और b चुनता है और यदि |a - b| ऐरे में नहीं है, तो खिलाड़ी इस संख्या को ऐरे में जोड़ देता है। जब कोई खिलाड़ी चाल नहीं चल पाता, तो वह हार जाता है। हमें खेल का विजेता ढूंढना है यदि खिलाड़ी P हमेशा खेल शुरू करता है।

इसलिए, यदि इनपुट A = [8, 9, 10] है, तो आउटपुट P होगा।

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

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

• n := len(arr)
• g := arr[0], max_val := arr[0]
• i को 1 से n-1 तक के लिए:
  • g := gcd(g, arr[i])
  • max_val := max(max_val, arr[i])
• total := (max_val / g) - n
• यदि total विषम है, तो 'P' लौटाएं।
• अन्यथा, 'Q' लौटाएं।

उदाहरण

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

from math import gcd

def who_is_the_winner(arr):
    n = len(arr)
    g = arr[0]
    max_val = arr[0]
    for i in range(1, n):
        g = gcd(g, arr[i])
        max_val = max(max_val, arr[i])
    total = (max_val / g) - n
    if total % 2 == 1:
        return 'P'
    return 'Q'

arr = [8, 9, 10]
print(who_is_the_winner(arr))

इनपुट

[8, 9, 10]

आउटपुट

P