Python में छिपे हुए सरणी में सबसे अधिक बार आने वाले तत्व का इंडेक्स खोजें

मान लीजिए, हमें 'TestArray' नामक एक क्लास दी गई है जिसमें एक प्राइवेट सरणी है जिसमें केवल 0 या 1 मान हो सकते हैं; और दो पब्लिक मेंबर फंक्शन length() और query()। फंक्शन length() सरणी की लंबाई वापस करता है और फंक्शन query() सरणी में विभिन्न मानों की तुलना करके तीन अलग-अलग मान वापस करता है। फंक्शन चार मान p, q, r, s इनपुट के रूप में लेता है और इस तरह काम करता है:

• यदि दिए गए इंडेक्स पर सरणी के सभी चार मान या तो 0 या 1 हैं, तो यह 4 वापस करता है।
• अन्यथा यदि दिए गए इंडेक्स पर सरणी के किन्हीं तीन मान समान हैं और चौथा मान अलग है, तो यह 2 वापस करता है।
• अन्यथा यदि दिए गए इंडेक्स पर सरणी में दो मान 0 और दो मान 1 हैं, तो यह 0 वापस करता है।

हमें सरणी को स्वयं एक्सेस किए बिना और केवल क्लास के मेंबर फंक्शन का उपयोग करके सरणी में सबसे अधिक बार आने वाले तत्व का इंडेक्स ढूंढना है। यदि सरणी में 0 और 1 की संख्या समान है, तो यह -1 वापस करता है।

इसलिए, यदि इनपुट है: array = [0, 1, 1, 0, 1, 1, 1, 0], तो आउटपुट 2 होगा। सरणी के इंडेक्स 2 पर मान 1 है जो सरणी में सबसे अधिक बार आने वाला मान है। इसी तरह, उत्तर 1, 4, 5, 6 भी सही हैं क्योंकि उन इंडेक्स में भी मान 1 है।

हल करने के चरण

1. n := length()
2. groupA := 1, groupB := 0
3. aIdx := null, bIdx := null
4. first := query(0, 1, 2, 3)
5. second := query(0, 1, 2, 4)
6. i को 4 से n तक के लिए:
   • यदि query(0, 1, 2, i), first के समान है, तो: groupA++, aIdx := i
   • अन्यथा: groupB++, bIdx := i
7. i को 0 से 2 तक के लिए:
   • nxt := नई सूची
   • v को 1 से 4 तक के लिए:
     • यदि v, i के समान नहीं है, तो nxt के अंत में v जोड़ें
   • यदि query(nxt के मान), second के समान है, तो: groupA++, aIdx := i
   • अन्यथा: groupB++, bIdx := i
8. यदि groupA > groupB, तो aIdx वापस करें
9. अन्यथा यदि groupB > groupA, तो bIdx वापस करें
10. अन्यथा, -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