লুকানো অ্যারেতে সবচেয়ে বেশি ফ্রিকোয়েন্ট এলিমেন্টের ইনডেক্স বের করা

মান লজিয়ে, 'TestArray' নামে একটি ক্লাস আছে যাতে একটি প্রাইভেট অ্যারে রয়েছে (শুধু 0 বা 1 মান ধারণ করতে পারে)। এতে দুটি পাবলিক মেম্বার ফাংশন আছে: length() এবং query()। length() অ্যারের দৈর্ঘ্য রিটার্ন করে। query() চারটি ইনডেক্স (p, q, r, s) নেয় এবং নিচেরভাবে কাজ করে:

• যদি চারটি ইনডেক্সের সব মান 0 বা 1 হয়, তবে 4 রিটার্ন করে।

• যদি তিনটি মান একই এবং একটা ভিন্ন হয়, তবে 2 রিটার্ন করে।

• যদি দুটি 0 এবং দুটি 1 থাকে, তবে 0 রিটার্ন করে।

অ্যারে সরাসরি এক্সেস না করেই শুধু এই মেম্বার ফাংশনগুলো ব্যবহার করে সবচেয়ে বেশি ফ্রিকোয়েন্ট এলিমেন্টের (0 বা 1) ইনডেক্স বের করতে হবে। যদি 0 এবং 1 সমান সংখ্যক থাকে তবে -1 রিটার্ন করবে।

ইনপুট: array = [0, 1, 1, 0, 1, 1, 1, 0] → আউটপুট: 2। ইনডেক্স 2-এ মান 1 যা সবচেয়ে বেশি ফ্রিকোয়েন্ট। ইনডেক্স 1, 4, 5, 6 ও সঠিক উত্তর।

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

• n := length()

• groupA := 1, groupB := 0

• aIdx := null, bIdx := null

• first := query(0, 1, 2, 3)

• second := query(0, 1, 2, 4)

• i = 4 থেকে n পর্যন্ত লুপ:

  • যদি query(0, 1, 2, i) == first, তবে groupA++, aIdx = i
  • অন্যথায় groupB++, bIdx = i

• i = 0 থেকে 2 পর্যন্ত লুপ:

  • nxt লিস্ট তৈরি করুন [0,1,2,3,4] থেকে i বাদ দিয়ে
  • যদি query(nxt) == second, তবে groupA++, aIdx = i
  • অন্যথায় groupB++, bIdx = i

• যদি groupA > groupB, তবে aIdx রিটার্ন করুন

• যদি groupB > groupA, তবে bIdx রিটার্ন করুন (নোট: মূল কোডে aIdx রিটার্ন করা হয়েছে, সম্ভবত বাগ)

• অন্যথায় -1 রিটার্ন করুন

উদাহরণ (Python)

class TestArray:
    def __init__(self, array) -> None:
        self.__arr = array
    def length(self):
        return len(self.__arr)
    def query(self, p, q, r, s):
        val = self.__arr[p] + self.__arr[q] + self.__arr[r] + self.__arr[s]
        if val == 4 or val == 0:
            return 4
        elif val == 1 or val == 3:
            return 2
        elif val == 2:
            return 0

def solve(reader):
    n, groupA, groupB, aIdx, bIdx = reader.length(), 1, 0, None, None
    first, second = reader.query(0,1,2,3), reader.query(0,1,2,4)
    for i in range(4, n):
        if reader.query(0,1,2,i) == first:
            groupA, aIdx = groupA+1, i
        else:
            groupB, bIdx = groupB+1, i
    for i in range(3):
        nxt = [v for v in [0,1,2,3,4] if v != i]
        if reader.query(*nxt) == second:
            groupA, aIdx = groupA+1, i
        else:
            groupB, bIdx = groupB+1, i
    return aIdx if groupA > groupB else bIdx if groupB > groupA else -1

arr_ob = TestArray([0, 1, 1, 0, 1, 1, 1, 0])
print(solve(arr_ob))

ইনপুট

[0, 1, 1, 0, 1, 1, 1, 0]

আউটপুট

2