C++ का उपयोग करके अंकगणितीय प्रगति में लापता संख्या

मान लीजिए हमारे पास एक ऐरे है जो क्रम में अंकगणितीय प्रगति के तत्वों को दर्शाता है। एक तत्व लापता है। हमें लापता तत्व ढूंढना है। तो यदि arr = [2, 4, 8, 10, 12, 14], आउटपुट 6 है, क्योंकि 6 लापता है।

बाइनरी सर्च का उपयोग करके, हम इस समस्या को हल कर सकते हैं। हम मध्य तत्व पर जाएंगे, फिर जांचेंगे कि मध्य और मध्य के बगल वाले के बीच का अंतर diff के समान है या नहीं। यदि नहीं, तो लापता तत्व इंडेक्स mid और mid + 1 के बीच मौजूद है। यदि मध्य तत्व AP में n/2वां तत्व है, तो लापता तत्व दाएं आधे में स्थित है, अन्यथा बाएं आधे में।

उदाहरण (C++)

#include <iostream> 
using namespace std; 

#define INT_MAX 999999 

class Progression { 
public: 
    int missingUtil(int arr[], int left, int right, int diff) { 
        if (right <= left) 
            return INT_MAX; 
        
        int mid = left + (right - left) / 2; 
        
        if (arr[mid + 1] - arr[mid] != diff) 
            return (arr[mid] + diff); 
        
        if (mid > 0 && arr[mid] - arr[mid - 1] != diff) 
            return (arr[mid - 1] + diff); 
        
        if (arr[mid] == arr[0] + mid * diff) 
            return missingUtil(arr, mid + 1, right, diff); 
        
        return missingUtil(arr, left, mid - 1, diff); 
    } 
    
    int missingElement(int arr[], int n) { 
        int diff = (arr[n - 1] - arr[0]) / n; 
        return missingUtil(arr, 0, n - 1, diff); 
    } 
}; 

int main() { 
    Progression pg; 
    int arr[] = {2, 4, 8, 10, 12, 14}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    cout << "The missing element is: " << pg.missingElement(arr, n) << endl; 
}

इनपुट

[2,4,8,10,12,14]

आउटपुट

The missing element is: 6