అన్ని సబ్‌రేలను 0 మొత్తంతో ముద్రించండి


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

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

ఉదాహరణ

అన్ని సబ్‌రేలను 0 మొత్తంతో ముద్రించండి

arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

అల్గారిథం

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

వివరణ

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

తాత్కాలిక మొత్తాన్ని కీగా మరియు వెక్టర్‌ను విలువగా కలిగి ఉన్న మ్యాప్‌ను మేము సృష్టిస్తాము. కాబట్టి, ఇక్కడ వెక్టర్ ఇన్పుట్ ప్రారంభం నుండి మూలకాల మొత్తం ప్రస్తుత మొత్తానికి సమానమైన సూచికలను సూచిస్తుంది.

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

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

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

మరియు దీని నుండి, మేము వెక్టర్గా ప్రకటించిన మా జాబితాను తిరిగి ఇస్తాము. అక్కడ నుండి రిటర్న్ విలువ పరిమాణం 0 కలిగి ఉంటే దాని అర్థం వేరే అవుట్పుట్ ముద్రించబడదని మేము కనుగొన్నాము.

అన్ని సబ్‌రేలను 0 మొత్తంతో ముద్రించడానికి సి ++ కోడ్

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
  unordered_map<int, vector<int> > Map;
  vector <pair<int, int>> result;
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    sum += arr[i];
    if (sum == 0)
      result.push_back(make_pair(0, i));
        if (Map.find(sum) != Map.end())
    {
      vector<int> vec = Map[sum];
      for (auto val = vec.begin(); val != vec.end(); val++)
        result.push_back(make_pair(*val + 1, i));
    }
    Map[sum].push_back(i);
  }
  return result;
}
void print(vector<pair<int, int>> result)
{
  for (auto j= result.begin(); j != result.end(); j++)
    cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
    int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
  vector<pair<int, int> > result = getSubArray(arr, n);
  if (result.size() == 0)
    cout << "No such Sub-array exists";
  else
    print(result);

  return 0;
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

అన్ని సబ్‌రేలను 0 మొత్తంతో ముద్రించడానికి జావా కోడ్

import java.util.*;
class Pair
{
    int start, end;
    Pair(int a, int b)
    {
        start = a;
        end = b;
    }
}
class printSubArray0Sum
{
    public static ArrayList<Pair> getSubArray(int[] arr, int n)
    {
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Pair> temp = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
                temp.add(new Pair(0, i));
            ArrayList<Integer> list = new ArrayList<>();
            if (map.containsKey(sum))
            {
                list = map.get(sum);
                for (int j = 0; j < list.size(); j++)
                {
                    temp.add(new Pair(list.get(j) + 1, i));
                }
            }
            list.add(i);
            map.put(sum, list);
        }
        return temp;
    }
    public static void print(ArrayList<Pair> result)
    {
        for (int i = 0; i < result.size(); i++)
        {
            Pair pair = result.get(i);
            System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
        }
    }
    public static void main(String args[])
    {
        int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
        int n = arr.length;

        ArrayList<Pair> result = getSubArray(arr, n);
        if (result.size() == 0)
            System.out.println("No such Sub-array exists");
        else
            print(result);
    }
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

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

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

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.

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

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య.