C++ का उपयोग करके 1 से n-1 के बीच एकमात्र दोहराव वाला तत्व खोजना

समस्या विवरण

इस समस्या में, हमें आकार N की एक अव्यवस्थित सरणी arr[] दी गई है जिसमें 1 से N-1 तक के मान होते हैं जिसमें एक मान सरणी में दो बार आता है। हमारा कार्य 1 से n-1 के बीच एकमात्र दोहराव वाला तत्व खोजना है।

उदाहरण

इनपुट

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

आउटपुट

1

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

विधि 1: नेस्टेड लूप (O(N²))

समस्या का एक सरल समाधान सरणी को पार करना और प्रत्येक मान के लिए यह जांचना है कि क्या तत्व सरणी में कहीं और मौजूद है। दोहरी घटना वाले मान को वापस करें।

#include <iostream> 
using namespace std; 

int findRepValArr(int arr[], int n) {
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(arr[i] == arr[j])
                return arr[i];
    return -1;
}

int main() {
    int arr[] = {5, 3, 2, 6, 6, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में दोहराव वाला मान है " << findRepValArr(arr, n);
    return 0;
}

विधि 2: गणितीय सूत्र (O(N)) - इष्टतम

समस्या को हल करने का एक अन्य दृष्टिकोण इस तथ्य का उपयोग करना है कि सरणी में दोहराव वाला मान, सरणी के योग से 1 से (N-1) तक के सभी पूर्णांकों के योग को घटाकर पाया जाता है।

पहली N-1 प्राकृतिक संख्याओं का योग (Sₙ) = N×(N-1)/2
दोहरा मान = arrSum - Sₙ

#include <iostream> 
using namespace std; 

int findRepValArr(int arr[], int n) {
    int arrSum = 0;
    for(int i = 0; i < n; i++)
        arrSum += arr[i];
    
    int sn = (n * (n - 1)) / 2;
    return arrSum - sn;
}

int main() {
    int arr[] = {5, 3, 2, 6, 6, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "सरणी में दोहराव वाला मान है " << findRepValArr(arr, n);
    return 0;
}

आउटपुट

सरणी में दोहराव वाला मान है 6

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

नोट

गणितीय दृष्टिकोण काम करता है क्योंकि सरणी में 1 से N-1 तक की सभी संख्याएं और एक अतिरिक्त डुप्लिकेट होती है। अपेक्षित योग से वास्तविक योग का अंतर डुप्लिकेट होता है।