ਸਾਰੀਆਂ ਉਪਨਗਰਾਂ ਨੂੰ 0 ਜੋੜ ਦੇ ਨਾਲ ਪ੍ਰਿੰਟ ਕਰੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਫ੍ਰੀਚਾਰਜ ਅਸਲ ਵਿੱਚ ਜਾਣਕਾਰੀ ਕੋਨਾ Microsoft ਦੇ ਓਏ ਕਮਰੇ
ਅਰੇ ਹੈਸ਼

ਤੁਹਾਨੂੰ ਪੂਰਨ ਅੰਕ ਦੀ ਐਰੇ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ, ਤੁਹਾਡਾ ਕੰਮ ਸਾਰੇ ਸੰਭਾਵਤ ਉਪ-ਐਰੇ ਨੂੰ ਜੋੜ ਕੇ 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. ਕੁਝ ਵੇਰੀਏਬਲ ਵਾਲੇ ਐਰੇ ਐਲੀਮੈਂਟਸ ਦਾ ਜੋੜ ਲੱਭੋ, ਜੋੜ ਜੋੜ ਦੇ ਨਾਲ ਸਬ-ਐਰੇ ਦਾ ਰਿਕਾਰਡ ਰੱਖਣ ਲਈ "Sum" ਕਹੋ.
  2. If ਜੋੜ 0 ਪਾਇਆ ਜਾਂਦਾ ਹੈ ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਮੌਜੂਦਾ ਸਬ-ਐਰੇ 0 ਤੋਂ ਮੌਜੂਦਾ ਇੰਡੈਕਸ ਤੱਕ ਪਾਈ ਗਈ ਹੈ.
  3. ਚੈੱਕ ਕਰੋ ਕਿ ਕੀ ਜੋੜ ਜੋ ਉਪਰੋਕਤ ਪ੍ਰਕਿਰਿਆ ਤੋਂ ਪਾਇਆ ਜਾਂਦਾ ਹੈ, ਸਾਡੇ ਵਿਚ ਮੌਜੂਦ ਹੈ ਨਕਸ਼ਾ ਜ ਨਾ.
  4. ਜੇ ਨਕਸ਼ੇ ਵਿੱਚ ਜੋੜ ਸ਼ਾਮਲ ਹੈ, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਇਹ ਪਿਛਲੀ ਉਪ-ਐਰੇ ਦਾ ਕੁੱਲ ਜੋੜ ਸੀ ਅਤੇ ਹੁਣ ਮੌਜੂਦਾ ਸੂਚਕਾਂਕਾਂ ਤਕ ਇਹ ਤੱਤ ਦਾ ਜੋੜ ਬਣ ਜਾਂਦਾ ਹੈ.
  5. ਨਕਸ਼ੇ ਵਿਚ ਮੌਜੂਦਾ ਜੋੜ ਪਾਓ ਜੇ ਇਹ ਪਹਿਲਾਂ ਤੋਂ ਮੌਜੂਦ ਨਹੀਂ ਸੀ.

ਕਥਾ

ਅਸੀਂ ਵਰਤਣ ਜਾ ਰਹੇ ਹਾਂ ਹੈਸ਼ਿੰਗ ਕਿਉਂਕਿ, ਇਸਦੇ ਨਾਲ, ਅਸੀਂ ਉਪ-ਐਰੇ ਅਤੇ ਉਨ੍ਹਾਂ ਦੇ ਸੂਚਕਾਂਕਾਂ 'ਤੇ ਨਜ਼ਰ ਰੱਖ ਸਕਦੇ ਹਾਂ. ਨਾਲ ਹੀ, ਅਸੀਂ ਵੱਖ-ਵੱਖ ਸੰਗ੍ਰਹਿ ਦੀ ਵਰਤੋਂ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ. ਪਹਿਲਾਂ, ਸਾਨੂੰ ਐਰੇ ਵਿਚਲੇ ਸਾਰੇ ਨੰਬਰ ਲੱਭਣੇ ਪੈਣਗੇ ਜੋ ਸੰਭਾਵਤ ਉਪ-ਐਰੇ ਨੂੰ ਜੋੜ ਕੇ 0 ਨਾਲ ਜੋੜਦੇ ਹਨ. ਉਸ ਲਈ, ਅਸੀਂ ਐਰੇ ਦੇ ਤੱਤ ਜੋੜਾਂਗੇ ਅਤੇ ਇਸ ਨੂੰ ਜੋੜ ਕੇ ਰੱਖਾਂਗੇ. ਰਕਮ ਦੀ ਸ਼ੁਰੂਆਤ ਤੇ ਪਹਿਲਾਂ ਹੀ ਅਰੰਭ ਕੀਤੀ ਜਾ ਰਹੀ ਸੀ.

ਅਸੀਂ ਇਕ ਨਕਸ਼ਾ ਬਣਾਵਾਂਗੇ ਜਿਸ ਵਿਚ ਅਸਥਾਈ ਜੋੜ ਦੀ ਕੁੰਜੀ ਹੈ ਅਤੇ ਮੁੱਲ ਵਜੋਂ ਇਕ ਵੈਕਟਰ. ਤਾਂ, ਵੈਕਟਰ ਇੱਥੇ ਸੂਚਕਾਂਕ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ ਜਿਸ ਤੇ ਇੰਪੁੱਟ ਦੀ ਸ਼ੁਰੂਆਤ ਤੋਂ ਤੱਤ ਦੀ ਜੋੜ ਮੌਜੂਦਾ ਰਕਮ ਦੇ ਬਰਾਬਰ ਹੁੰਦੀ ਹੈ.

ਇਸ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਨਾ ਸ਼ੁਰੂ ਕਰਦੇ ਹਾਂ. ਇਸ ਲਈ, ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਅੱਗੇ ਵਧਦੇ ਹਾਂ ਅਸੀਂ ਤੱਤ ਨੂੰ ਪਰਿਵਰਤਨਸ਼ੀਲ ਰਕਮ ਵਿੱਚ ਜੋੜਨਾ ਜਾਰੀ ਰੱਖਦੇ ਹਾਂ. ਜੇ ਰਕਮ ਕਿਸੇ ਵੀ ਪਲ 0 ਪਾਇਆ ਜਾਂਦਾ ਹੈ. ਤਾਂ, ਇਸਦਾ ਅਰਥ ਇਹ ਹੈ ਕਿ ਅਰੰਭ ਤੋਂ ਸਬ-ਐਰੇ 0 ਹੈ. ਅਤੇ ਇਹ ਵੀ ਜੇ ਕੁਝ ਸੂਚਕ ਮਿਲ ਗਏ ਹਨ ਜਿਨ੍ਹਾਂ ਦੀ ਜੋੜ 0 ਦੇ ਬਰਾਬਰ ਸੀ.

ਜੇ ਜੋੜ ਜ਼ੀਰੋ ਨਹੀਂ ਪਾਇਆ ਜਾਂਦਾ. ਫਿਰ ਅਸੀਂ ਜਾਂਚ ਕਰਦੇ ਹਾਂ ਕਿ ਕੀ ਨਕਸ਼ੇ ਵਿੱਚ ਉਹ ਜੋੜ ਹੈ. ਜੇ ਨਕਸ਼ੇ ਵਿੱਚ ਗਣਨਾ ਕੀਤੀ ਰਕਮ ਸ਼ਾਮਲ ਨਹੀਂ ਹੈ. ਫਿਰ ਇੱਥੇ ਕੋਈ ਉਪਨਗਰੀ ਮੌਜੂਦ ਨਹੀਂ ਹੈ ਜੋ ਮੌਜੂਦਾ ਸੂਚਕਾਂਕ ਤੇ ਖਤਮ ਹੁੰਦੀ ਹੈ ਅਤੇ ਉਸਦਾ ਜੋੜ 0 ਹੁੰਦਾ ਹੈ. ਇਸ ਲਈ, ਸਾਰੀਆਂ ਉਪ-ਐਰੇ ਲੱਭਣ ਦੇ ਬਾਅਦ ਜੋ ਮੌਜੂਦਾ ਸੂਚਕਾਂਕ ਤੇ ਖਤਮ ਹੁੰਦੇ ਹਨ ਅਤੇ 0 ਦੇ ਬਰਾਬਰ ਹੁੰਦੇ ਹਨ. ਅਸੀਂ ਮੌਜੂਦਾ ਸੂਚਕਾਂਕ ਨੂੰ ਵੈਕਟਰ ਵਿਚ ਜੋੜਾਂਗੇ. ਕੁੰਜੀ ਦੇ ਤੌਰ ਤੇ ਮੌਜੂਦਾ ਜੋੜ ਹੈ, ਜੋ ਕਿ ਨਕਸ਼ੇ.

ਪਰ ਜੇ ਨਕਸ਼ੇ ਵਿਚ ਜੋੜ ਹੈ ਤਾਂ ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਸਾਨੂੰ ਕੁਝ ਪਿਛਲੀਆਂ ਉਪ-ਐਰੇ ਮਿਲੀਆਂ ਸਨ ਜਿਨ੍ਹਾਂ ਦੀ ਇਕੋ ਰਕਮ ਸੀ. ਤਦ ਸਾਨੂੰ ਉਸ ਜੋੜ ਅਤੇ ਸੂਚਕਾਂਕ ਦਾ ਮੁੱਲ ਜੋੜਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਅਤੇ ਇਸ ਵਿਚੋਂ, ਅਸੀਂ ਆਪਣੀ ਸੂਚੀ ਵਾਪਸ ਕਰਦੇ ਹਾਂ ਜਿਸ ਨੂੰ ਅਸੀਂ ਇਕ ਵੈਕਟਰ ਵਜੋਂ ਘੋਸ਼ਿਤ ਕੀਤਾ ਸੀ. ਉੱਥੋਂ ਜੇ ਰਿਟਰਨ ਵੈਲਯੂ ਦਾ ਆਕਾਰ 0 ਹੈ ਤਾਂ ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਸਾਨੂੰ ਨਹੀਂ ਮਿਲਿਆ ਕਿ ਕੁਝ ਵੀ ਆਉਟਪੁਟ ਪ੍ਰਿੰਟ ਨਹੀਂ ਹੋਵੇਗਾ.

C ++ ਕੋਡ ਸਾਰੇ ਉਪਨਗਰਾਂ ਨੂੰ 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) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.