पायथन में ऐरे से न्यूनतम हटाकर GCD बढ़ाएं

मान लीजिए हमारे पास N संख्याओं की एक सूची है। हमें वह न्यूनतम संख्या ढूंढनी है जिन्हें हटाने के बाद शेष संख्याओं का GCD, मूल N संख्याओं के प्रारंभिक GCD से बड़ा हो जाए।

इसलिए, यदि इनपुट [6, 9, 15, 30] है, तो आउटपुट 2 होगा क्योंकि प्रारंभिक GCD 3 है, और 6 और 9 को हटाने के बाद GCD 15 हो जाता है, जो 3 से बड़ा है।

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

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

INF := 100001
spf := [0, 1, ..., INF] (सबसे छोटा अभाज्य गुणनखंड सरणी)।
sieve() फ़ंक्शन परिभाषित करें:
- i को 4 से INF तक 2 से बढ़ाते हुए: spf[i] := 2
- i को 3 से INF तक के लिए:
  - यदि i² > INF, तो ब्रेक करें।
  - यदि spf[i] == i, तो:
    - j को 2*i से INF तक i से बढ़ाते हुए:
      - यदि spf[j] == j, तो spf[j] := i
calc_fact(x) फ़ंक्शन परिभाषित करें:
- ret := []
- जब तक x != 1:
  - ret.append(spf[x])
  - x := x // spf[x]
- ret लौटाएं।
मुख्य विधि से:
- g := 0
- i को 0 से n-1 तक: g := gcd(a[i], g)
- my_map := {}
- i को 0 से n-1 तक: a[i] := a[i] // g
- i को 0 से n-1 तक:
  - p := calc_fact(a[i])
  - s := {}
  - j को 0 से len(p)-1 तक: s[p[j]] := 1
  - s में प्रत्येक i के लिए: my_map[i] := my_map.get(i, 0) + 1
- minimum := 10⁹
- my_map में प्रत्येक i के लिए:
  - first := i, second := my_map[i]
  - यदि (n - second) <= minimum, तो minimum := n - second
- यदि minimum != 10⁹, तो minimum लौटाएं।
- अन्यथा, -1 लौटाएं।

उदाहरण

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

from math import gcd as __gcd

INF = 100001
spf = [i for i in range(INF)]

def sieve():
    for i in range(4, INF, 2):
        spf[i] = 2
    for i in range(3, INF):
        if i ** 2 > INF:
            break
        if spf[i] == i:
            for j in range(2 * i, INF, i):
                if spf[j] == j:
                    spf[j] = i

def calc_fact(x):
    ret = []
    while x != 1:
        ret.append(spf[x])
        x = x // spf[x]
    return ret

def minRemove(a, n):
    g = 0
    for i in range(n):
        g = __gcd(a[i], g)
    my_map = {}
    for i in range(n):
        a[i] = a[i] // g
    for i in range(n):
        p = calc_fact(a[i])
        s = {}
        for j in range(len(p)):
            s[p[j]] = 1
        for i in s:
            my_map[i] = my_map.get(i, 0) + 1
    minimum = 10 ** 9
    for i in my_map:
        first = i
        second = my_map[i]
        if (n - second) <= minimum:
            minimum = n - second
    if minimum != 10 ** 9:
        return minimum
    else:
        return -1

a = [6, 9, 15, 30]
n = len(a)
sieve()
print(minRemove(a, n))

इनपुट

[6, 9, 15, 30], 4