मान लीजिए हमारे पास दो सरणियाँ हैं जो एक-दूसरे की डुप्लिकेट हैं सिवाय एक तत्व के, तो, दिए गए सरणियों में से एक से एक तत्व गायब है, हमें उस लापता तत्व को ढूंढना है।
तो, यदि इनपुट A = [2, 5, 6, 8, 10], B = [5, 6, 8, 10] की तरह है, तो आउटपुट 2 होगा क्योंकि 2 दूसरी सरणी से गायब है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन solve() परिभाषित करें। यह A, B, N लेगा
यदि N, 1 के समान है, तो
A[0] वापस करें;
यदि A[0], B[0] के समान नहीं है, तो
A[0] वापस करें
low := 0, high := N - 1
जब low < high, करें
mid := (low + high) / 2
यदि A[mid], B[mid] के समान है, तो
low := mid
अन्यथा,
high := mid
यदि low, high - 1 के समान है, तो
लूप से बाहर निकलें
A[high] वापस करें
मुख्य विधि से, निम्नलिखित करें -
M := A का आकार, N := B का आकार
यदि N, M-1 के समान है, तो
solve(A, B, M) वापस करें
अन्यथा जब M, N-1 के समान है, तो
solve(B, A, N) वापस करें
अन्यथा,
"Not found" वापस करें
उदाहरण
बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
def solve(A, B, N): if N == 1: return A[0]; if A[0] != B[0]: return A[0] low = 0 high = N - 1 while (low < high): mid = (low + high) / 2 if A[mid] == B[mid]: low = mid else: high = mid if low == high - 1: break return A[high] def get_missing_element(A, B): M = len(A) N = len(B) if N == M-1: return solve(A, B, M) elif M == N-1: return solve(B, A, N) else: return "Not found" A = [2, 5, 6, 8, 10] B = [5, 6, 8, 10] print(get_missing_element(A, B))
इनपुट
[2, 5, 6, 8, 10], [5, 6, 8, 10]
आउटपुट
2