দেওয়া যোগফল যুক্ত সাবঅ্যারে খুঁজে বের করা (নেগেটিভ নাম্বার হ্যান্ডেল করে) C++-এ

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

উদাহরণ

সমস্যাটি বুঝতে একটি উদাহরণ নিই:

ইনপুট : arr[] = {2, 5, -1, 4, 6, -9, 5} sum = 14
আউটপুট : subarray = {5, -1, 4, 6}

ব্যাখ্যা:

সাবঅ্যারে যোগফল = 5 - 1 + 4 + 6 = 14

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

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

অ্যালগরিদম

স্টেপ ১ − অ্যারেতে লুপ চালান, i → 0 থেকে (n-1) পর্যন্ত।
- স্টেপ ১.১ − প্রতিটি উপাদানের জন্য, সব সম্ভাব্য সাবঅ্যারেতের যোগফল বের করুন।
- স্টেপ ১.২ − যদি বর্তমান সাবঅ্যারে উপাদানগুলোর যোগফল দেওয়া সাবঅ্যারের সমান হয়, তবে সাবঅ্যারেটি প্রিন্ট করুন।
স্টেপ ২ − যদি অ্যারেতার সব উপাদান ট্রাভার্স হয়ে যায় এবং কোনো সাবঅ্যারে না পাওয়া যায়। "No subarray with the given sum found!" প্রিন্ট করুন।

উদাহরণ প্রোগ্রাম (নেস্টেড লুপ পদ্ধতি)

আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:

#include <bits/stdc++.h>
using namespace std;

void printSubArray(int arr[], int i, int j) {
    cout << "{ ";
    for (; i < j; i++)
        cout << arr[i] << " ";
    cout << "}";
}

int findSubArrayWithSum(int arr[], int n, int sum) {
    int currSum;
    for (int i = 0; i < n; i++) {
        currSum = arr[i];
        for (int j = i + 1; j <= n; j++) {
            if (currSum == sum) {
                cout << "Subarray with given sum : ";
                printSubArray(arr, i, j);
                return 1;
            }
            if (currSum > sum || j == n)
                break;
            currSum = currSum + arr[j];
        }
    }
    cout << "No subarray found";
    return 0;
}

int main() {
    int arr[] = { 2, 5, -1, 4, 6, -9, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 14;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

আউটপুট

Subarray with given sum : { 5 -1 4 6 }

উন্নত পদ্ধতি (হ্যাশম্যাপ ব্যবহার করে)

এই সমস্যা সমাধানের একটি ভালো পদ্ধতি হল হ্যাশম্যাপ ব্যবহার করা। হ্যাশম্যাপটি বর্তমান ইনডেক্স পর্যন্ত প্রিফিক্স যোগফল সংরক্ষণ করবে। এবং যেকোনো ইনডেক্সের জন্য, চেক করব যে যোগফল যুক্ত কোনো সাবঅ্যারে আছে কি না। আমরা চেক করব যে কোনো প্রিফিক্স আছে কিনা যার যোগফল = sum - value।

উদাহরণ প্রোগ্রাম (হ্যাশম্যাপ পদ্ধতি)

#include <bits/stdc++.h>
using namespace std;

void printSubArray(int arr[], int i, int j) {
    cout << "{ ";
    for (; i <= j; i++)
        cout << arr[i] << " ";
    cout << "}";
}

void findSubArrayWithSum(int arr[], int n, int sum) {
    unordered_map<int, int> map;
    int curr_sum = 0;
    for (int i = 0; i < n; i++) {
        curr_sum = curr_sum + arr[i];
        if (curr_sum == sum) {
            cout << "SubArray with the given sum :";
            printSubArray(arr, 0, i);
            return;
        }
        if (map.find(curr_sum - sum) != map.end()) {
            cout << "SubArray with the given sum : ";
            printSubArray(arr, map[curr_sum - sum] + 1, i);
            return;
        }
        map[curr_sum] = i;
    }
    cout << "No subarray found!";
}

int main() {
    int arr[] = { 2, 5, -1, 4, 6, 9, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 14;
    findSubArrayWithSum(arr, n, sum);
    return 0;
}

আউটপুট

SubArray with the given sum : { 5 -1 4 6 }