পাইথনে O(n) সময় ও O(1) অতিরিক্ত স্পেসে সর্বোচ্চ পুনরাবৃত্ত সংখ্যা খুঁজে বের করা

একটি অ্যারে দেওয়া আছে যার আকার n, এবং উপাদানগুলো 0 থেকে k-1 পরিসরের মধ্যে (k ≤ n)। অতিরিক্ত স্পেস ছাড়া O(n) সময়ে সর্বোচ্চ বার পুনরাবৃত্ত হওয়া সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট: k = 8, A = [3, 4, 4, 6, 4, 5, 2, 8]

আউটপুট: 4 (কারণ ৪ তিনবার এসেছে)

সমাধানের পদ্ধতি

1. অ্যারেটি ইন-প্লেস (in-place) মডিফাই করা হয়।
2. প্রতিটি উপাদান A[i]-র জন্য, ইনডেক্স (A[i] % k) এর মানকে k দিয়ে বাড়ানো হয়।
3. শেষে যে ইনডেক্সের মান সবচেয়ে বড়, সেই ইনডেক্সই সর্বোচ্চ পুনরাবৃত্ত সংখ্যা।
4. কারণ যেই সংখ্যাটি z বার এসেছে, ইনডেক্স z-তে k*z যোগ হয়েছে।

পাইথন কোড

def get_max_repeating(A, k):
    n = len(A)
    for i in range(n):
        A[A[i] % k] += k
    
    max_val = A[0]
    result = 0
    for i in range(1, n):
        if A[i] > max_val:
            max_val = A[i]
            result = i
    return result

A = [3, 4, 4, 6, 4, 5, 2, 8]
k = 8
print(get_max_repeating(A, k))

ইনপুট

[3, 4, 4, 6, 4, 5, 2, 8], 8

আউটপুট

4