C++ में दो समीकरणों का उपयोग करके दोहराने वाला और लापता संख्या खोजना

समस्या विवरण

इस समस्या में, हमें आकार N की एक सरणी arr[] दी गई है। इसमें 1 से N तक के पूर्णांक मान होते हैं। और रेंज से एक तत्व x गायब है जबकि सरणी में एक तत्व y दो बार आता है। हमारा कार्य दो समीकरणों का उपयोग करके दोहराने वाला और लापता संख्या खोजना है।

उदाहरण

इनपुट

arr[] = {1, 2, 3, 3}

आउटपुट

लापता = 4, दोहराने वाला = 3

हल का दृष्टिकोण

समस्या को हल करने की एक विधि x और y दो मानों के लिए दो समीकरणों का उपयोग करना है। फिर x और y के मान प्राप्त करने के लिए समीकरण को हल करें।

समीकरण निर्माण

सरणी के तत्वों का योग पहले N प्राकृतिक संख्याओं के योग के बराबर होता है जिसमें एक तत्व अतिरिक्त और एक लापता होता है।

arrSum = Sum(N) - x + y
y - x = arrSum - Sum(N)          // समीकरण 1

अब, वर्ग योग लें। इसी तरह,

arrSqSum = SqSum(N) - x² + y²
(y - x)(y + x) = arrSqSum - SqSum(N)

समीकरण 1 का उपयोग करके,

x + y = (arrSqSum - SqSum(N)) / (arrSum - Sum(N))    // समीकरण 2

दोनों समीकरणों को जोड़ने पर हमें मिलता है

y = [(arrSqSum - SqSum(N)) / (arrSum - Sum(N)) + (arrSum - Sum(N))] / 2

फिर y के मान का उपयोग करके, हम x को खोजेंगे:

x = y - (arrSum - Sum(N))

हमारे पास सूत्र हैं:

Sum(N) = N(N+1)/2
SqSum(N) = N(N+1)(2N+1)/6

C++ कार्यान्वयन

#include <iostream> 
using namespace std; 

void findExtraAndMissingVal(int arr[], int n) {
    int sumN = (n * (n + 1)) / 2;
    int sqSumN = (n * (n + 1) * (2 * n + 1)) / 6;
    
    int arrSum = 0, arrSqSum = 0;
    for (int i = 0; i < n; i++) {
        arrSum += arr[i];
        arrSqSum += (arr[i] * arr[i]);
    }
    
    int diff = arrSum - sumN;           // y - x
    int sqDiff = arrSqSum - sqSumN;     // y² - x²
    int sumXY = sqDiff / diff;          // y + x
    
    int y = (sumXY + diff) / 2;         // दोहराने वाला
    int x = y - diff;                   // लापता
    
    cout << "सरणी से लापता मान है " << x << endl;
    cout << "सरणी में दो बार आने वाला मान है " << y;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    findExtraAndMissingVal(arr, n);
    return 0;
}

आउटपुट

सरणी से लापता मान है 5
सरणी में दो बार आने वाला मान है 2

जटिलता विश्लेषण

• समय जटिलता: O(N)
• स्पेस जटिलता: O(1)

महत्वपूर्ण नोट

यह दृष्टिकोण O(1) अतिरिक्त स्पेस का उपयोग करता है और पूर्णांक ओवरफ्लो को संभालता है (बड़े N के लिए लॉन्ग लॉन्ग का उपयोग करें)। यह मानता है कि ठीक एक संख्या दोहराई गई है और एक लापता है।