C++-এ অ্যারেতে অ্যারে যোগফলের অর্ধেক সমান এলিমেন্ট আছে কিনা তা খুঁজুন

এই সমস্যায়, আমাদের একটি সোর্টেড ইউনিক মানগুলোর অ্যারে দেওয়া আছে। আমাদের কাজ হল অ্যারেতে এমন একটি এলিমেন্ট খুঁজে বের করা যার মান অ্যারে যোগফলের অর্ধেক।

সমস্যা বিবরণ: অ্যারে arr[]-এ, আমাদের এমন একটি এলিমেন্ট x খুঁজে বের করতে হবে যাতে অ্যারের সব এলিমেন্টের যোগফল 2*x-এর সমান হয়।

উদাহরণ দিয়ে বুঝি,

ইনপুট: arr[] = {2, 4, 5, 6, 7}

আউটপুট: না

ব্যাখ্যা:

যোগফল = 2 + 4 + 5 + 6 + 7 = 24

কোনো এলিমেন্ট পাওয়া যায়নি।

সমাধানের পদ্ধতি:

সমস্যাটি সমাধান করতে আমাদের সিম্পলি এমন এলিমেন্ট খুঁজে বের করতে হবে যা সব এলিমেন্টের যোগফলের অর্ধেক।

অ্যালগরিদম:

1. ধাপ ১: অ্যারের সব এলিমেন্টের যোগফল বের করুন।
2. ধাপ ২: যোগফল বিজোড় হলে -1 রিটার্ন করুন।
3. ধাপ ৩: যোগফল জোড় হলে, x খুঁজুন যাতে x*2 = যোগফল।
4. ধাপ ৪: এলিমেন্ট পাওয়া গেলে ১ রিটার্ন করুন।
   ধাপ ৫: এলিমেন্ট না পাওয়া গেলে -1 রিটার্ন করুন।

এলিমেন্ট সার্চের জন্য বাইনারি সার্চ অ্যালগরিদম ব্যবহার করা যাবে কারণ অ্যারেটি সোর্টেড।

সমাধান দর্শানোর প্রোগ্রাম,

উদাহরণ

#include <iostream> 
using namespace std; 

int checkForElement(int array[], int n) { 
    int arrSum = 0; 
    for (int i = 0; i < n; i++) 
        arrSum += array[i]; 
    if (arrSum % 2) 
        return -1; 
    int start = 0; 
    int end = n - 1; 
    while (start <= end) 
    { 
        int mid = start + (end - start) / 2; 
        if ((2 * array[mid]) == arrSum) 
            return array[mid]; 
        else if ((2 * array[mid]) > arrSum) 
            end = mid - 1; 
        else 
            start = mid + 1; 
    } 
    return -1; 
} 

int main() { 
    int array[] = { 4, 5, 6, 7, 9 }; 
    int n = sizeof(array) / sizeof(array[0]); 
    int x = checkForElement(array, n); 
    if(x != -1) 
        cout << "Element found, value is " << x; 
    else 
        cout << "Element not found!"; 
    return 0; 
}

আউটপুট

Element not found!