পাইথনে অ্যারে থেকে ন্যূনতম অপসারণ করিয়ে GCD বড় করুন

সমস্যা বিবরণ

N সংখ্যার একটি লিস্ট দেওয়া আছে। এর প্রাথমিক GCD (সর্বোচ্চ সাধারণ ভাজক) থেকে বড় GCD পাওয়ার জন্য ন্যূনতম কতগুলো সংখ্যা অপসারণ করতে হবে তা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট [6, 9, 15, 30] হলে প্রাথমিক GCD হলো ৩। 6 এবং 9 অপসারণ করলে বাকি 15, 30-এর GCD হবে ১৫ যা ৩-এর চেয়ে বড়। সুতরাং আউটপুট 2।

সমাধানের ধাপসমূহ

1. INF := 100001 এবং spf (স্মলেস্ট প্রাইম ফ্যাক্টর) অ্যারে তৈরি করুন।
2. sieve() ফাংশন দিয়ে spf বের করুন (সিভ অফ এরাটোস্থেনিস)।
3. calc_fact(x) ফাংশন দিয়ে x-এর প্রাইম ফ্যাক্টরগুলো বের করুন।
4. মূল পদ্ধতিতে:
   • সর্বোচ্চ সাধারণ ভাজক g বের করুন।
   • প্রতিটি উপাদানকে g দিয়ে ভাগ করুন।
   • প্রতিটি উপাদানের প্রাইম ফ্যাক্টর বের করে ফ্রিকোয়েন্সি ম্যাপ my_map বানান।
   • সর্বাধিক ফ্রিকোয়েন্সি वाले প্রাইম ফ্যাক্টর খুঁজুন; minimum := n - max_frequency।
   • যদি সম্ভব হয়, 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 * i > 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 //= 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] //= g
    for i in range(n):
        p = calc_fact(a[i])
        s = {}
        for val in p:
            s[val] = 1
        for val in s:
            my_map[val] = my_map.get(val, 0) + 1
    minimum = 10**9
    for val, freq in my_map.items():
        if (n - freq) <= minimum:
            minimum = n - freq
    if minimum != 10**9:
        return minimum
    else:
        return -1

a = [6, 9, 15, 30]
n = len(a)
sieve()
print(minRemove(a, n))  # আউটপুট: 2

ইনপুট

[6, 9, 15, 30], 4

আউটপুট

2