প্রদত্ত অঙ্কের সাথে সাববারে সন্ধান করুন (নেতিবাচক নম্বরগুলি পরিচালনা করে)


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক কুপনডুনিয়া Delhivery জিই হেলথকেয়ার তথ্যপ্রযুক্তি মুনফ্রোগ ল্যাব
বিন্যাস কাটা সহচরী উইন্ডোতে

"প্রদত্ত সমষ্টি (হ্যান্ডেল নেতিবাচক নম্বরগুলি সহ) সহকারে সন্ধান করুন" সমস্যাটি বলে যে আপনাকে একটি দেওয়া হয়েছে পূর্ণসংখ্যা বিন্যাস, পাশাপাশি negativeণাত্মক পূর্ণসংখ্যা এবং "সমষ্টি" নামক একটি সংখ্যা রয়েছে। সমস্যা বিবরণী সাব-অ্যারে মুদ্রণ করতে বলে, যা "যোগফল" নামক একটি নির্দিষ্ট সংখ্যার সমষ্টি su যদি আমাদের আউটপুট হিসাবে একাধিক সাব-অ্যারে উপস্থিত থাকে তবে সেগুলির যে কোনও একটি মুদ্রণ করুন।

উদাহরণ

প্রদত্ত অঙ্কের সাথে সাববারে সন্ধান করুন (নেতিবাচক নম্বরগুলি পরিচালনা করে)

arr[] = {2,4,-2,3,1}
sum = 1
Sum found between index 2 to index 3
arr[] = {12,10,-20,30,1}
sum = 20
Sum found between index 1 to index 3
arr[] = {2,4,-2,3,1}
sum = -1
No such sub-array exists.

অ্যালগরিদম

  1. ঘোষণা করুন ক মানচিত্র.
  2. সেট কারেন্টসাম 0 তে
  3. অ্যারে অতিক্রম করুন, যখন আমি <এন,
    1. কারেন্টসাম এবং অ্যারে উপাদানটির মান যোগ করে এবং এটি বর্তমানের সুমে সঞ্চয় করে।
    2. কারেন্টসম যোগফলের সমান কিনা তা পরীক্ষা করে দেখুন।
      • যদি সত্য হয় তবে সূচকটি 0 থেকে i হিসাবে মুদ্রণ করুন এবং বিরতি দিন।
    3. মানচিত্রটিতে কারেন্ট সুম-যোগফল রয়েছে কিনা তা পরীক্ষা করুন।
      • যদি সত্য হয় তবে সূচকগুলি মানচিত্রে বর্তমানের সুম মান হিসাবে I এবং বিরতিতে মুদ্রণ করুন।
    4. যদি প্রদত্ত শর্তের কোনওটি সন্তুষ্ট না হয়, এর অর্থ আমরা প্রদত্ত পরিমাণের সাথে কিছুই পাইনি।

ব্যাখ্যা

আমাদের একটি সমস্যা বিবৃতি দেওয়া হয়েছে যা প্রদত্ত পরিমাণের পরিমাণের সাব-অ্যারে খুঁজে বের করতে বলে এবং যদি সেখানে একাধিক সাব-অ্যারে পাওয়া যায়, তবে সেগুলির যে কোনও একটি মুদ্রণ করুন। আমরা ব্যবহার করতে যাচ্ছি হ্যাশ মানচিত্র এবং আমরা এর মান সংরক্ষণ করতে যাচ্ছি কারেন্টসাম এবং এর সূচক যদি প্রতিটি উপাদান যুক্ত করার পরে কোনও শর্ত সন্তুষ্ট হয় না বিন্যাস এবং কারেন্টসাম (যা আগে 0 হিসাবে শুরু হয়েছিল)।

আসুন একটি উদাহরণ বিবেচনা করুন:

উদাহরণ

অ্যারে [] = {14, 1, -10, 20, 1}, যোগ = 5 XNUMX

আমরা একটি পূর্ণসংখ্যার অ্যারে দিয়েছি যা কিছু নেতিবাচক পূর্ণসংখ্যার পাশাপাশি এবং সংখ্যার যোগ করে। আমাদের উপ-অ্যারে খুঁজে বের করতে হবে যা প্রদত্ত সংখ্যা, যোগফল যোগ করে। পুরো অ্যারেটি অতিক্রম করার সময় আমাদের আমাদের বর্তমানসামটি বজায় রাখা উচিত, এটি আমাদের সম্ভাব্য সাব-অ্যারে দেয়।

i = 0, কারেন্টসাম = 0

কারেন্টসাম = কারেন্টসাম + আরআর [i] => কারেন্টসাম = ১৪, এখন আমাদের কারেন্টসমে 14 রয়েছে, আমরা এটি পরীক্ষা করে দেখব যে এটি প্রদত্ত যোগফলের সমান কিনা 14 এবং এটি মিথ্যা, তবে আমরা মানচিত্রটিতে রয়েছে কিনা তা পরীক্ষা করব কারেন্টসাম-যোগ অর্থ 5-14 = 5 টিও মিথ্যা। সুতরাং আমরা পরবর্তী উপাদান মাধ্যমে যেতে হবে। সুতরাং আমরা মানচিত্রে কারেন্টসাম এবং আমি যুক্ত করব।

i = 1, কারেন্টসাম = 14

কারেন্টসাম = কারেন্টসাম + আরআর [i] => ১৪ + ১ = ১৫, কারেন্টসাম = ১৫, এখন আমাদের কারেন্টসমে 14 আছে, আমরা এটি প্রদত্ত রাশির সমান কিনা তা পরীক্ষা করব তবে এটি সন্তুষ্ট নয়, আমরা যদি যাব তবে মানচিত্রে বর্তমানের যোগফল রয়েছে যা 1-15-15 হয় এটিও মিথ্যা। সুতরাং আমরা মানচিত্রে কারেন্টসাম এবং আমি যুক্ত করব।

i = 2, কারেন্টসাম = 15,

কারেন্টসাম = কারেন্টসাম + আরআর [i] => 15 + (-10), কারেন্টসাম = 5, এখন আমাদের কারেন্টসামে 15 রয়েছে, আমরা এটি পরীক্ষা করে দেখব যে এটি প্রদত্ত পরিমাণের 5 এর সমান কিনা এবং আমরা দেখতে পেলাম যে শর্তটি সন্তুষ্ট, এর অর্থ আমরা আমাদের আউটপুট পেয়েছি, তারপরে আমরা সাবহারে 0 থেকে i এর সূচিগুলি মুদ্রণ করব।

কোড

প্রদত্ত অঙ্কের সাথে সাববারি সন্ধানের জন্য সি ++ কোড (নেতিবাচক নম্বরগুলি পরিচালনা করে)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}
Sum found between index 0 to index 2

প্রদত্ত অঙ্কের সাথে সাববারি সন্ধানের জন্য জাভা কোড (নেতিবাচক নম্বরগুলি পরিচালনা করে)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}
Sum found between index 0 to index 2

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

চালু) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।