සියලුම උපසිරැසි 0 එකතුවකින් මුද්‍රණය කරන්න


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් FreeCharge ඇත්ත වශයෙන්ම තොරතුරු එජ් මයික්රොසොෆ්ට් OYO කාමර
අරා හැෂ්

ඔබට පූර්ණ සංඛ්‍යා අරාවක් ලබා දී ඇත, ඔබේ කර්තව්‍යය වනුයේ හැකි සියලුම උප අරා එකතුව 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 ප්‍රමාණයෙන් තිබේ නම් එයින් අදහස් වන්නේ වෙනත් කිසිවක් ප්‍රතිදානය මුද්‍රණය නොකරන බවයි.

C ++ කේතය 0 උපසිරැසි XNUMX ක් සමඟ මුද්‍රණය කිරීමට

#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 උපසිරැසි XNUMX ක් සමඟ මුද්‍රණය කිරීමට

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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.