0 बेरीजसह सबर्रे आहे का ते शोधा  


अडचण पातळी मध्यम
वारंवार विचारले सिट्रिक्स डीई शॉ गोल्डमन Sachs खरंच मेकमायट्रिप ओयओ रूम्स पेटीएम टीसीएस
अरे हॅश

"0 बेरीजसह सबअरे आहे की नाही हे शोधा" या समस्येमध्ये असे म्हटले आहे की आपणास पैसे दिले गेले आहेत पूर्णांक अॅरे तसेच नकारात्मक पूर्णांक असतात. समस्या विधानात कमीतकमी १ आकाराचे कोणतेही उप-अ‍ॅरे निर्धारित करण्यास सांगितले जाते. या उप-अ‍ॅरेची बेरीज 1 समान असणे आवश्यक आहे.

उदाहरण  

0 बेरीजसह सबर्रे आहे का ते शोधा

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

स्पष्टीकरण

येथे निर्देशांक 0 ते 2 मधील घटकांची बेरीज 0 आहे.

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

स्पष्टीकरण

0 ची उप-अ‍ॅरे विद्यमान नाही.

अल्गोरिदम  

  1. घोषित ए सेट करा.
  2. आरंभ करा बेरीज 0 पर्यंत.
  3. अ‍ॅरेचा आडवा करा, तर मी <एन (अ‍ॅरेची लांबी).
    1. अररमध्ये बेरीज जोडा [i] आणि बेरीज करण्यासाठी ती संचयित करा.
    2. पुढीलपैकी कोणतीही परिस्थिती सत्य आहे का ते तपासा:
      1. बेरीज == 0 / अर [i] == 0 / सेटमध्ये बेरीजचे मूल्य असते.
      2. जर ते खरे असेल तर सत्य परत करा.
    3. सेटमध्ये बेरीज जोडा.
  4. खोटे परत.

स्पष्टीकरण

आम्हाला एक समस्या स्टेटमेंट मिळाली आहे जी 0 च्या बरोबरीने कोणतीही उप-अ‍ॅरे अस्तित्त्वात आहे की नाही हे शोधण्यासाठी विचारते, हे सोडवण्यासाठी आम्ही या समस्येचे निराकरण करण्यासाठी सेट वापरू. आम्ही दिलेल्या अ‍ॅरेचे घटक सेटमध्ये संग्रहित करणार आहोत. नंतर एकाच वेळी बेरीजमध्ये व्हॅल्यू जोडा आणि सेटमध्ये सध्याच्या बेरीजसह उप-अ‍ॅरेची काही जुळवाजुळव आहे की नाही हे तपासा. जर बेरीज 0 सह उप-अ‍ॅरे असल्याचे आढळले तर आम्ही परत येऊ. खरे.

जर एखाद्या उप-अ‍ॅरेपैकी 0 ची बेरीज आढळली नाहीत तर आपण लूपमधून चुकीचे परत मिळवू. तसेच एक गोष्ट आहे, जर घटकांपैकी कोणतेही एक 0 असेल तर आपण देखील सत्य परत येऊ कारण घटक स्वतः एका घटकाची उप-अ‍ॅरे आहे. तर याचा अर्थ असा आहे की आम्हाला अशी एक उप-अ‍ॅरे सापडली आहे.

हे सुद्धा पहा
के पेक्षा मोठे किंवा समान प्राइम फ्रिक्वेन्सी सह संख्या

येथे कोडमध्ये आपण बुलियन फंक्शन घोषित करतो, ते एकतर बरोबर किंवा खोटे परत मिळवते, जर उप-अ‍ॅरे आढळल्यास ते खरे परत मिळते, अन्यथा ते चुकीचे दिसेल.

चला त्याचं उदाहरण घेऊ:

उदाहरण

अरे [] = {- 3,2,1,9,6}

येथे कोडमध्ये आपण अ‍ॅरेचा माग काढत आहोत आणि बेरीज आणि अ‍ॅर [i] जोडू आणि त्या तपासणीनंतर जर बेरीज == ० किंवा अरर [i] 0 किंवा सेटमध्ये बेरीजचे मूल्य असेल तर दिलेली कोणतीही अट पूर्ण झाल्यास आम्ही सत्य परत येऊ आणि नंतर सेटमध्ये बेरीज करू.

उप-अ‍ॅरेपैकी काहीही आढळले नाही तर आम्ही चुकीचे परत येऊ.

बेरीज = 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 अट येथे संतुष्ट झाली आहे, तर आम्ही ख return्या अर्थाने परत येऊ, याचा अर्थ आम्हाला बेरीज 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

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. हे सर्व हॅशसेट वापरल्यामुळे शक्य झाले कारण ते आम्हाला ओ (1) वेळेत घालण्याची, शोध घेण्याची, हटविण्याची परवानगी देते.

हे सुद्धा पहा
स्टॉक II लीटकोड सोल्यूशन खरेदी आणि विक्री करण्याचा सर्वोत्तम वेळ

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. तयार केलेल्या हॅश सेटमध्ये जास्तीत जास्त एन घटक असू शकतात, म्हणून स्पेसची जटिलता रेखीय असते.