मान लीजिए, हमें 'TestArray' नामक एक क्लास दी गई है जिसमें एक सरणी है जो अन्य क्लास द्वारा एक्सेस नहीं की जा सकती और दो पब्लिक मेंबर फंक्शन length() और compare()। फंक्शन length() सरणी की लंबाई वापस करता है और फंक्शन compare() सरणी से विभिन्न सबएरे की तुलना करके तीन अलग-अलग मान वापस करता है। फंक्शन चार मान l, r, x, y इनपुट के रूप में लेता है और इस तरह काम करता है:
- यदि (array[l] + ... + array[r]) > (array[x] + ... + array[y]), तो यह 1 वापस करता है
- यदि (array[l] + ... + array[r]) = (array[x] + ... + array[y]), तो यह 0 वापस करता है
- यदि (array[l] + ... + array[r]) < (array[x] + ... + array[y]), तो यह -1 वापस करता है
हमें सरणी को स्वयं एक्सेस किए बिना और केवल क्लास के मेंबर फंक्शन का उपयोग करके सरणी में अधिकतम तत्व का इंडेक्स ढूंढना है।
इसलिए, यदि इनपुट है: array = [8, 4, 2, 12, 11, 8, 4, 2, 7], तो आउटपुट 3 होगा। सरणी में सबसे बड़ा तत्व 12 है और यह इंडेक्स 3 पर स्थित है।
हल करने के चरण
- n := length()
- low := 0, high := n - 1
- जब low < high:
- mid := (low + high + 1) // 2 का फ्लोर वैल्यू
- यदि (low + high + 1) % 2 == 0:
- res := compare(low, mid-1, mid, high)
- यदि res == 1, तो high := mid - 1
- अन्यथा low := mid
- अन्यथा:
- res := compare(low, mid-1, mid+1, high)
- यदि res == 1, तो high := mid - 1
- अन्यथा यदि res == -1, तो low := mid + 1
- अन्यथा, mid वापस करें
- यदि high == low, तो high वापस करें
- -1 वापस करें
उदाहरण (Python)
class TestArray:
def __init__(self, array) -> None:
self.__arr = array
def length(self):
return len(self.__arr)
def compare(self, l, r, x, y):
val1 = sum(i for i in self.__arr[l:r+1])
val2 = sum(j for j in self.__arr[x:y+1])
if val1 > val2:
return 1
elif val1 == val2:
return 0
elif val1 < val2:
return -1
def solve(reader):
n = reader.length()
low, high = 0, n - 1
while low < high:
mid = (low + high + 1) // 2
if (low + high + 1) % 2 == 0:
res = reader.compare(low, mid-1, mid, high)
if res == 1: high = mid - 1
else: low = mid
else:
res = reader.compare(low, mid-1, mid+1, high)
if res == 1: high = mid - 1
elif res == -1: low = mid + 1
else: return mid
if high == low: return high
return -1
arr_ob = TestArray([8, 4, 2, 12, 11, 8, 4, 2, 7])
print(solve(arr_ob))
इनपुट
[8, 4, 2, 12, 11, 8, 4, 2, 7]
आउटपुट
3