Sum of Max and Min

Company Interviews Question Using C++

Complete Code :

#include <iostream>
#include <vector>

struct MinMax {
    int minimum;
    int maximum;
};

MinMax findMinMax(const std::vector<int>& arr, int left, int right) {
    MinMax result;
    
    // If the array contains only one element
    if (left == right) {
        result.minimum = arr[left];
        result.maximum = arr[left];
    } else if (left == right - 1) {
        // If the array contains two elements, compare them
        result.minimum = std::min(arr[left], arr[right]);
        result.maximum = std::max(arr[left], arr[right]);
    } else {
        // If the array has more than two elements, divide and conquer
        int mid = (left + right) / 2;
        MinMax leftPart = findMinMax(arr, left, mid);
        MinMax rightPart = findMinMax(arr, mid + 1, right);
        
        // Combine the results from left and right parts
        result.minimum = std::min(leftPart.minimum, rightPart.minimum);
        result.maximum = std::max(leftPart.maximum, rightPart.maximum);
    }
    
    return result;
}

int main() {
    std::vector<int> arr = {3, 5, 4, 1, 9};
    int n = arr.size();
    
    if (n == 0) {
        std::cout << "Array is empty." << std::endl;
        return 0;
    }
    
    MinMax result = findMinMax(arr, 0, n - 1);
    
    std::cout << "Minimum element is: " << result.minimum << std::endl;
    std::cout << "Maximum element is: " << result.maximum << std::endl;
    
    return 0;
}

MinMax Function :

struct MinMax {
    int minimum;
    int maximum;
};

English :

The heart of this algorithm lies in the findMinMax function, which uses a divide-and-conquer approach to minimize the number of comparisons.

• const std::vector<int>& arr is the array to be processed.
• int left and int right are the indices representing the current segment of the array that we are analyzing.

Hindi :

इस कार्यक्रम की मूल विधि findMinMax में स्थित है, जो तुलनाओं की संख्या को कम करने के लिए एक बाँटने-और-नियंत्रण का उपयोग करती है।

• const std::vector<int>& arr सरणी को प्रोसेस करने के लिए है।
• int left और int right वे सूचक हैं जो हमारे द्वारा विश्लेषण किए जा रहे वर्ग का प्रतीक हैं।

Hinglish :

Is algorithm ki kernal findMinMax function mein sthapit hai, jo nyuntam tulnaon ko kam karne ke liye ek vibhajit aur adhikar abhigyan upayog karta hai.

• const std::vector<int>& arr vah sarray hai jise prakriya kiya jata hai.
• int left aur int right vah soochak hain jo hamare dvara anusandhan kiye ja rahe sarray ke vishesh kshetra ko darust karte hain.

result.minimum = std::min(leftPart.minimum, rightPart.minimum);
result.maximum = std::max(leftPart.maximum, rightPart.maximum);

English :

Within the findMinMax function, we handle three main scenarios:

If the array segment contains only one element (left == right), then that element is both the minimum and maximum. We set the result.minimum and result.maximum to that element.

1. If the array segment contains two elements (left == right - 1), we compare these two elements and set result.minimum and result.maximum accordingly.
2. If there are more than two elements in the array segment, we divide it into two parts by calculating the mid index. Then, we recursively call findMinMax on both the left and right segments.
3. After finding the minimum and maximum in both the left and right segments, we combine the results. The minimum of the two minimums becomes the minimum of the overall array, and the maximum of the two maximums becomes the maximum of the overall array.
4. The findMinMax function returns a MinMax struct with the minimum and maximum values for the given array segment.
5. In the main function, we create an array of integers named arr. You can replace this with your own array or input method.
6. We check if the array is empty. If it is, we print a message indicating that the array is empty.
7. If the array is not empty, we call the findMinMax function, passing the arr, and the starting and ending indices (0 and n - 1, where n is the size of the array).
8. Finally, we print the minimum and maximum values obtained from the findMinMax function.

The divide-and-conquer algorithm helps reduce the number of comparisons compared to a simple linear search, making it an efficient way to find both the minimum and maximum elements in an array.

Hindi :

1. findMinMax फ़ंक्शन के अंदर, हम तीन प्रमुख प्राधिकरणों को संभालते हैं:
2. अगर सरणी सेगमेंट में केवल एक मात्र तत्व होता है (left == right), तो वह तत्व न्यूनतम और अधिकतम दोनों होता है। हम result.minimum और result.maximum को उस तत्व के बराबर सेट करते हैं।
3. अगर सरणी सेगमेंट में दो तत्व होते हैं (left == right - 1), तो हम इन दो तत्वों की तुलना करते हैं और result.minimum और result.maximum को उनके अनुसार सेट करते हैं।
4. यदि सरणी सेगमेंट में दो से अधिक तत्व हैं, तो हम इसे दो भागों में बाँटते हैं, mid सूची को हासिल करके। फिर हम पूर्ववत दाईं और बाईं सेगमेंट पर findMinMax को रिकर्सिव रूप से बुलाते हैं।
5. दोनों पूर्ववत दाईं और बाईं सेगमेंट में न्यूनतम और अधिकतम का पता लगाने के बाद, हम परिणामों को मिलाते हैं। दो न्यूनतमों में से किसी एक को दुरुस्तिबद्ध किया जाता है, वही सम्पूर्ण सरणी के न्यूनतम होता है, और दो अधिकतमों में से किसी एक को अधिकतम किया जाता है, वही सम्पूर्ण सरणी के अधिकतम होता है।
6. findMinMax फ़ंक्शन MinMax संरचना के साथ वर्ग के न्यूनतम और अधिकतम मानों के साथ लौटाता है, जिन्हें सारणी सेगमेंट के लिए प्राप्त किया गया है।
7. main फ़ंक्शन में, हम एक पूरे संख्याओं की सरणी बनाते हैं, जिसे arr नामक कर सकते हैं। आप इसे अपनी खुद की सरणी या इनपुट पद्धति से बदल सकते हैं।
8. हम यह जांचते हैं कि क्या सरणी खाली है। यदि यह ऐसा होता है, तो हम एक संदेश प्रिंट करते हैं जिसमें यह कहा गया होता है कि सरणी खाली है।
9. यदि सरणी खाली नहीं है, तो हम findMinMax फ़ंक्शन को बुलाते हैं, arr को पास करते हैं, और प्रारंभ और समापन सूचकों (0 और n - 1, जहां n सरणी का आकार है) को पास करते हैं।
10. आखिरकार, हम findMinMax फ़ंक्शन से प्राप्त न्यूनतम और अधिकतम मानों को प्रिंट करते हैं।

बाँटने और नियंत्रण का तरीका, एक सामान्य रूप से एक सामान्य रूप से तुलना खोज की तुलना में तुलनाओं की संख्या को कम करने में मदद करता है, और यह सरणी में न्यूनतम और अधिकतम तत्वों को ढूंढने के लिए एक प्रभावी तरीका है।

Hinglish :

1. findMinMax function ke andar, ham teen mukhya sthitiyon ka samavesh karte hain:
2. Yadi sarray kshetra mein keval ek tatv hai (left == right), to vah tatv nyuntam aur adhikatam dono hota hai. Hum result.minimum aur result.maximum ko us tatv ke barabar set karte hain.
3. Yadi sarray kshetra mein do tatv hain (left == right - 1), to ham in do tatvon ki tulna karte hain aur result.minimum aur result.maximum ko uske anuroop set karte hain.
4. Yadi sarray kshetra mein do se adhik tatv hain, to usse do bhagon mein vibhajit kiya jata hai, mid soochi prapt karke. Fir, ham purnvarti rup se findMinMax ko dono baen aur daen kshetron par bulate hain.
5. Baen aur daen kshetron mein nyuntam aur adhikatam ko prapt karne ke baad, ham un parinamon ko milate hain. Do nyuntamon mein se ek nyuntam sarray ka nyuntam banta hai aur do adhikamon mein se ek adhikam sarray ka adhikam banta hai.
6. findMinMax function sarray kshetra ke liye prapt nyuntam aur adhikatam mulyon ke sath ek MinMax struct ko vapas karta hai.
7. main function mein, ham ek puri sankhyaon ki sarray banate hain, jise arr ke naam se kaha ja sakta hai. Aap ise apni khud ki sarray ya input vidhi se badal sakte hain.
8. Ham dekhte hain ki kya sarray khali hai. Yadi hai, to ham ek sandesh chhapte hain jisme bataya jata hai ki sarray khali hai.
9. Yadi sarray khali nahi hai, to ham findMinMax function ko bulate hain, arr ko dete hain, aur shuruaat aur ant ke soochak (0 aur n - 1, jahan n sarray ka akar hai) ko dete hain.
10. Ant mein, ham findMinMax function se prapt nyuntam aur adhikatam mulyon ko chhapte hain.

Vibhajit aur adhikar abhigyan tulnaon ke tulya khoj ke mukable tulyaon ki sankhya ko kam karne mein madad karta hai, aur ek sarray mein nyuntam aur adhikatam tatv dhundhne ke liye yah ek prabhavit tarike se hai.