0 మొత్తంతో సబార్రే ఉందా అని కనుగొనండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది సిట్రిక్స్ డిఇ షా గోల్డ్మన్ సాచ్స్ నిజానికి MakeMyTrip OYO రూములు Paytm టీసీఎస్
అర్రే హాష్

“0 మొత్తంతో సబార్రే ఉందా అని కనుగొనండి” అనే సమస్య మీకు ఇవ్వబడింది పూర్ణ సంఖ్య అమరిక ప్రతికూల పూర్ణాంకాలను కలిగి ఉంటుంది. సమస్య స్టేట్మెంట్ కనీసం 1 పరిమాణంలో ఏదైనా ఉప-శ్రేణిని నిర్ణయించమని అడుగుతుంది. ఈ ఉప-శ్రేణి 1 కి సమానమైన మొత్తాన్ని కలిగి ఉండాలి.

ఉదాహరణ

0 మొత్తంతో సబార్రే ఉందా అని కనుగొనండి

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

వివరణ

ఇక్కడ, సూచిక 0 నుండి 2 వరకు మూలకాలు మొత్తం 0 కలిగి ఉంటాయి.

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

వివరణ

మొత్తం 0 ఉన్న ఉప-శ్రేణి ఏదీ లేదు.

అల్గారిథం

  1. ప్రకటించండి a సెట్.
  2. ప్రారంభించును మొత్తం 0 కు.
  3. అయితే, శ్రేణిని దాటండి i <n (శ్రేణి యొక్క పొడవు).
    1. Ar [i] కు మొత్తాన్ని జోడించి మొత్తానికి నిల్వ చేయండి.
    2. కింది షరతులు ఏమైనా నిజమో కాదో తనిఖీ చేయండి:
      1. sum == 0 / arr [i] == 0 / సెట్‌లో మొత్తం విలువ ఉంటే.
      2. నిజమైతే, తిరిగి నిజమైనది.
    3. సెట్‌కు మొత్తాన్ని జోడించండి.
  4. తప్పుడు తిరిగి.

వివరణ

0 కి సమానమైన మొత్తంతో ఏదైనా ఉప-శ్రేణి ఉందా అని తెలుసుకోవడానికి మాకు ఒక సమస్య స్టేట్మెంట్ వచ్చింది. దీనిని పరిష్కరించడానికి మేము ఈ సమస్యను పరిష్కరించడానికి ఒక సెట్ను ఉపయోగిస్తాము. మేము ఇచ్చిన శ్రేణి యొక్క మూలకాలను సెట్‌లో నిల్వ చేయబోతున్నాము. అప్పుడు ఏకకాలంలో మొత్తాన్ని విలువను జోడించి, సమితిలో ప్రస్తుత మొత్తంతో ఉప-శ్రేణి యొక్క ఏదైనా సరిపోలిక ఉందా లేదా మొత్తం 0 కి సమానం కాదా అని తనిఖీ చేయండి. మొత్తం 0 తో ఉప-శ్రేణి ఉన్నట్లు కనుగొనబడితే, అప్పుడు మేము తిరిగి వస్తాము నిజం.

ఉప-శ్రేణులలో ఏదీ మొత్తం 0 ఉన్నట్లు కనుగొనకపోతే, మేము లూప్ నుండి తప్పుడు తిరిగి ఇవ్వబోతున్నాము. అలాగే, ఒక విషయం ఉంది, ఏదైనా మూలకం 0 అయితే మనం కూడా నిజం అవుతాము ఎందుకంటే ఒక మూలకం ఒకే మూలకం యొక్క ఉప శ్రేణి. కాబట్టి మేము అలాంటి ఒక ఉప శ్రేణిని కనుగొన్నాము.

ఇక్కడ కోడ్‌లో, మేము బూలియన్ ఫంక్షన్‌ను ప్రకటిస్తాము, అది నిజం లేదా తప్పు అని తిరిగి వస్తుంది, ఉప-శ్రేణి కనుగొనబడితే, అది నిజం అవుతుంది, లేకపోతే అది తప్పుడు అవుతుంది.

ఒక ఉదాహరణను పరిశీలిద్దాం:

ఉదాహరణ

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

ఇక్కడ కోడ్‌లో, మేము ఒక శ్రేణిని దాటుతాము మరియు మొత్తాన్ని మరియు అర్ర్ [i] ను జోడించి మొత్తంగా నిల్వ చేస్తాము మరియు ఆ తనిఖీ తర్వాత, sum == 0 లేదా arr [i] 0 కి సమానం లేదా సెట్ మొత్తం విలువను కలిగి ఉంటే, ఇచ్చిన షరతులో ఏదైనా సంతృప్తికరంగా ఉంటే, అప్పుడు మేము నిజమైనదిగా తిరిగి, ఆపై మొత్తాన్ని సెట్‌లోకి చేర్చబోతున్నాము.

ఉప-శ్రేణి ఏదీ కనుగొనబడకపోతే, మేము తప్పుడు తిరిగి ఇవ్వబోతున్నాము.

sum = 0, సెట్ = {Set

i = 0, arr [i] = -3

sum = sum + arr [i] => 0 + - 3 = -3

sum == 0 లేదా arr [i] 0 కి సమానం లేదా సెట్ మొత్తం విలువను కలిగి ఉంటే, వాటిలో మూడు తప్పుడువి, కాబట్టి మేము ఇక్కడ ఏమీ చేయలేము మరియు -3 ను సెట్‌లోకి చేర్చుతాము.

i = 1, arr [i] = 2

sum = sum + arr [i] => -3 + 2 = -1

sum == 0 లేదా arr [i] 0 కి సమానం లేదా సెట్ మొత్తం విలువను కలిగి ఉంటే, వాటిలో మూడు తప్పుడువి, కాబట్టి మేము ఇక్కడ ఏమీ చేయలేము మరియు -1 ను సెట్‌లోకి చేర్చుతాము.

i = 2, arr [i] = 1

sum = sum + arr [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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై)  (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య. హ్యాష్‌సెట్‌ను ఉపయోగించడం వల్ల ఇవన్నీ సాధ్యమయ్యాయి ఎందుకంటే ఇది O (1) సమయంలో చొప్పించడానికి, శోధించడానికి, తొలగించడానికి అనుమతిస్తుంది.

అంతరిక్ష సంక్లిష్టత

పై)  (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య. సృష్టించిన హాష్ సెట్‌లో గరిష్టంగా n అంశాలు ఉండవచ్చు కాబట్టి, స్థల సంక్లిష్టత సరళంగా ఉంటుంది.