Python - ऐसी पॉजिटिव संख्या M ढूंढना जिससे gcd(N^M, N&M) अधिकतम हो

मान लीजिए हमारे पास एक संख्या N है, हमें एक पॉजिटिव संख्या M ढूंढनी है जिससे gcd(N^M, N&M) जितना संभव हो उतना बड़ा हो और m < n। हम प्राप्त किए गए सबसे बड़े gcd को भी लौटाएंगे।

तो, यदि इनपुट 20 जैसा है, तो आउटपुट 31 होगा।

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

• यदि bit_count(n), 0 के समान है, तो
  • i को 2 से int(sqrt(n)) + 1 तक रेंज में, करें
    • यदि n % i == 0, तो
      • int(n / i) लौटाएं
• अन्यथा,
  • val := 0
  • p := 1
  • dupn := n
  • जब n नॉन-ज़ीरो है, करें
    • यदि (n & 1) == 0, तो
      • val := val + p
    • p := p * 2
    • n := n >> 1
  • gcd(val ^ dupn, val & dupn) लौटाएं
• 1 लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें:

from math import gcd, sqrt

def bit_count(n):
    if n == 0:
        return 0
    else:
        return ((n & 1) == 0) + bit_count(n >> 1)

def maximum_gcd(n):
    if bit_count(n) == 0:
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                return int(n / i)
    else:
        val = 0
        p = 1
        dupn = n
        while n:
            if (n & 1) == 0:
                val += p
            p = p * 2
            n = n >> 1
        return gcd(val ^ dupn, val & dupn)
    return 1

n = 20
print(maximum_gcd(n))

इनपुट

20

आउटपुट

31