सर्व बेरीज 0 बेरीजसह मुद्रित करा


अडचण पातळी हार्ड
वारंवार विचारले ऍमेझॉन फ्रीचार्ज खरंच माहिती काठ मायक्रोसॉफ्ट ओयओ रूम्स
अरे हॅश

आपणास पूर्णांक अ‍ॅरे देण्यात आला आहे, आपले कार्य सर्व संभाव्य उप-अ‍ॅरेस ० सह बरोबरीने मुद्रित करणे आहे. म्हणून आपण सर्व उपनगरी 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

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

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.