0 যোগফল সহ একটি সাববারি আছে কিনা তা সন্ধান করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় Citrix ডিই শ গোল্ডম্যান শ্যাস প্রকৃতপক্ষে MakeMyTrip ওয় রুমগুলি Paytm TCS
বিন্যাস কাটা

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

উদাহরণ

0 যোগফল সহ একটি সাববারি আছে কিনা তা সন্ধান করুন

arr[] = {2,1,-3,4,5}
yes

ব্যাখ্যা

এখানে সূচক 0 থেকে 2 পর্যন্ত উপাদানগুলির যোগফল 0 হয়।

arr[] = {4,1,-4,5,1}
yes

ব্যাখ্যা

যোগফল নেই এমন কোন উপ-অ্যারে উপস্থিত নেই।

অ্যালগরিদম

  1. ঘোষণা করুন ক সেট.
  2. আরম্ভ সমষ্টি 0 তে
  3. অ্যারে অতিক্রম করুন, যখন i <এন (অ্যারের দৈর্ঘ্য)
    1. আরে যোগ যোগ করুন [i] এবং যোগফলটি এটি যোগ করুন।
    2. নিম্নলিখিত শর্তগুলির মধ্যে সত্য কিনা তা পরীক্ষা করুন:
      1. যোগ == 0 / আরআর [i] == 0 / যদি সেটটিতে যোগফলের মান থাকে।
      2. যদি সত্য হয় তবে সত্যে ফিরে আসুন।
    3. যোগফল যোগ করুন।
  4. মিথ্যা প্রত্যাবর্তন।

ব্যাখ্যা

আমরা একটি সমস্যার বিবৃতি পেয়েছি যা 0 এর সমান পরিমাণের সাথে কোনও উপ-অ্যারে রয়েছে কিনা তা জানতে চেয়েছিল এটি সমাধান করার জন্য আমরা এই সমস্যাটি সমাধান করার জন্য একটি সেট ব্যবহার করব। আমরা একটি নির্দিষ্ট অ্যারের উপাদানগুলি সেটে সংরক্ষণ করতে যাচ্ছি। তারপরে একই সাথে যোগফলের সাথে মান যোগ করুন এবং সেটে বর্তমান যোগফলের সাথে উপ-অ্যারের কোনও মিল রয়েছে কিনা তা পরীক্ষা করুন বা যোগফলটি 0 সমান হবে যদি সেখানে 0 যোগফলের সাথে উপ-অ্যারে হিসাবে পাওয়া যায় তবে আমরা ফিরে আসব সত্য।

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

এখানে কোডে, আমরা একটি বুলিয়ান ফাংশন ঘোষণা করি, এটি সত্য বা মিথ্যা প্রত্যাবর্তন করবে, যদি সাব-অ্যারে পাওয়া যায় তবে এটি সত্য ফিরে আসে, অন্যথায় এটি মিথ্যা ফিরে আসবে।

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

উদাহরণ

আরআর [] = {- 3,2,1,9,6}

এখানে কোডটিতে আমরা একটি অ্যারে অনুসরণ করব এবং যোগফল এবং অ্যারে যুক্ত করব [i] এবং যোগফল এবং এই পরীক্ষার পরে যদি যোগ == 0 বা অ্যারের [i] সমান হয় বা যোগফলের মান থাকে, যদি প্রদত্ত শর্তের কোনওটি সন্তুষ্ট হয় তবে আমরা সত্যটিতে ফিরে যাব এবং তারপরে সেটটিতে যোগফল যোগ করব।

যদি সাব-অ্যারেগুলির কোনওটি না পাওয়া যায় তবে আমরা মিথ্যাতে ফিরে যাব।

যোগফল = 0, সেট =}

i = 0, এআর [i] = -3

যোগফল = যোগ + আরআর [i] => 0 + - 3 = -3

যদি যোগ == 0 বা আরার [i] 0 এর সমান হয় বা সেটে যোগফলের মান থাকে, তন্মধ্যে তিনটি মিথ্যা, তাই আমরা এখানে কিছুই করি না এবং সেটটিতে -3 যোগ করি।

i = 1, অ্যারে [i] = 2

যোগফল = যোগ + আরআর [i] => -3 + 2 = -1

যদি যোগ == 0 বা আরার [i] 0 এর সমান হয় বা সেটে যোগফলের মান থাকে, তন্মধ্যে তিনটি মিথ্যা, তাই আমরা এখানে কিছুই করি না এবং সেটটিতে -1 যোগ করি।

i = 2, অ্যারে [i] = 1

যোগফল = যোগ + আরআর [i] => -1 + 1 = 0

যদি যোগ == 0 শর্তটি এখানে সন্তুষ্ট হয়, তাই আমরা সত্যটিতে ফিরে আসি, এর অর্থ আমরা যোগফল 0 সহ একটি উপ-অ্যারে পেয়েছি।

আউটপুট: হ্যাঁ, যোগফল 0 সহ একটি উপ-অ্যারে বিদ্যমান।

কোড

0 টি যোগফল সহ একটি সাববারি আছে কিনা তা সন্ধান করতে সি ++ কোড

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

জাভা কোডটি খুঁজে পেতে সেখানে 0 যোগফল সহ একটি সাববারি আছে কিনা

import java.util.Set;
import java.util.HashSet;

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

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

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। এই সমস্ত কিছুই হ্যাশসেট ব্যবহারের কারণে সম্ভব হয়েছিল কারণ এটি আমাদের ও (1) সময়ে সন্নিবেশ, অনুসন্ধান, মোছার কাজ করতে দেয়।

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু তৈরি হ্যাশ সেটে সর্বাধিক n উপাদান থাকতে পারে, তাই স্পেস জটিলতা রৈখিক।