সি++ প্রোগ্রাম: অ্যারেতে ফ্যাক্টোরিয়ালের যোগফল নির্ণয়

একটি সর্টেড (sorted) অ্যারে A দেওয়া থাকলে, যেখানে সব উপাদান দুবার করে রয়েছে কিন্তু একটি উপাদান শুধু একবার রয়েছে। সেই একক উপাদানটি বের করতে হবে। যদি অ্যারে [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9] হয়, তবে একক উপাদানটি ৫।

এটি বাইনারি সার্চ (binary search) দিয়ে সমাধান করা যাবে। একক উপাদানের আগে সব উপাদানের প্রথম অকারেন্স (occurrence) ইনডেক্স ০, ২, ৪...-এ থাকে এবং দ্বিতীয় অকারেন্স ১, ৩, ৫...-এ। কিন্তু একক উপাদানের পর সব উপাদানের প্রথম অকারেন্স বিজোড় ইনডেক্সে এবং দ্বিতীয় অকারেন্স জোড় ইনডেক্সে থাকবে।

মধ্যে মিড (mid) ইনডেক্স বের করে, যদি mid জোড় হয়, তবে A[mid] এবং A[mid+1] তুলনা করা, একই হলে লেফ্ট বা রাইটে যাওয়া। আর যদি mid বিজোড় হয়, তবে A[mid] এবং A[mid-1] তুলনা করা, একই হলে লেফ্ট বা রাইটে যাওয়া।

উদাহরণ

#include<iostream> using namespace std; void findSingleElement(int *arr, int left, int right) {    if (left > right)       return;    if (left==right) {       cout << "The required element is: "<< arr[left];       return;    }    int mid = (left + right) / 2;    if (mid%2 == 0) {       if (arr[mid] == arr[mid+1])          findSingleElement(arr, mid+2, right);       else          findSingleElement(arr, left, mid);    }else{       if (arr[mid] == arr[mid-1])          findSingleElement(arr, mid+1, right);       else          findSingleElement(arr, left, mid-1);    } } int main() {    int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};    int len = sizeof(arr)/sizeof(arr[0]);    findSingleElement(arr, 0, len-1); }

আউটপুট

The required element is: 5