ఇచ్చిన శ్రేణి కోసం అన్ని ప్రత్యేకమైన ఉప-శ్రేణి మొత్తాన్ని కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గ్రేఆరెంజ్ Intuit మైక్రోసాఫ్ట్ నాగరో
అర్రే హాష్ సార్టింగ్

మీకు పూర్ణాంకాల శ్రేణి ఉందని అనుకుందాం. “ఇచ్చిన శ్రేణి కోసం అన్ని ప్రత్యేకమైన ఉప-శ్రేణి మొత్తాల మొత్తాన్ని కనుగొనండి” సమస్య అన్ని ప్రత్యేకమైన ఉప-శ్రేణుల మొత్తాన్ని తెలుసుకోవడానికి అడుగుతుంది (ఉప-శ్రేణి మొత్తం ప్రతి ఉప-శ్రేణి యొక్క మూలకాల మొత్తం).

ప్రత్యేకమైన ఉప-శ్రేణి మొత్తం ద్వారా, ఉప-శ్రేణికి ఒకే విలువ లేదని మేము చెప్పాము.

ఉదాహరణ

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

ఇచ్చిన శ్రేణి కోసం అన్ని ప్రత్యేకమైన ఉప-శ్రేణి మొత్తాన్ని కనుగొనండి

అల్గారిథం

  1. ప్రకటించండి a చిహ్నం.
  2. సెట్ అవుట్పుట్ కు 0.
  3. శ్రేణిని i = 0 నుండి i వరకు ప్రయాణించండి
    1. ఏర్పరచు మొత్తం 0 కు.
    2. శ్రేణిని j = i నుండి j వరకు ప్రయాణించండి
      • మొత్తానికి arr [j] విలువను జోడించండి.
      • మ్యాప్‌లో మొత్తం మరియు దాని సంభవం జోడించండి.
  4. మ్యాప్‌లో ప్రయాణించి, ఆ కీ యొక్క ఎంట్రీల విలువ 1 అని తనిఖీ చేయండి.
    1. మేము పరిస్థితి సంతృప్తికరంగా ఉన్నప్పుడల్లా అవుట్‌పుట్‌కు కీల విలువను జోడించండి.
  5. రిటర్న్ అవుట్పుట్.

వివరణ

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

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

ఉదాహరణ

arr [] = {3, 1, 4, 5}

మొదట, మనకు i = 0 ఉంది, తరువాత మనకు 3 మూలకం ఉంది మరియు మేము 3 నుండి ప్రారంభిస్తాము, మేము మొత్తంలో 3 ని జోడించి 3 ను మ్యాప్‌లోకి అప్‌డేట్ చేస్తాము, తరువాత మొత్తంలో 1 ని జోడించి, 4 ను మ్యాప్‌లోకి అప్‌డేట్ చేస్తాము , ఆపై మొత్తాన్ని 4 గా మూలకంగా తీసుకొని 7 ను మ్యాప్‌లోకి చేర్చండి. ఈ విధంగా, మేము 5 ని సందర్శించి, 12 ను మ్యాప్‌లోకి అప్‌డేట్ చేసిన తర్వాత మొదటి ట్రావెర్సల్‌ను ముగించాము.

కాబట్టి మేము 4 ను ఒక మూలకంగా తీసుకొని 4 నుండి ప్రారంభించినప్పుడు, మొత్తాన్ని మ్యాప్‌లోకి అప్‌డేట్ చేస్తాము, ఎందుకంటే, 4 ఇప్పటికే ఉంది చిహ్నం, మేము దాని ఫ్రీక్వెన్సీని పెంచుతాము మరియు ఫ్రీక్వెన్సీ 1 లేని మొత్తాలను మేము విస్మరిస్తాము. ఈ విధంగా, మేము ప్రత్యేకమైన ఉప-శ్రేణులను నిర్వహించగలుగుతాము.

కోడ్

ఇచ్చిన శ్రేణి కోసం అన్ని ప్రత్యేకమైన ఉప-శ్రేణి మొత్తాన్ని కనుగొనడానికి C ++ కోడ్

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}
44

ఇచ్చిన శ్రేణి కోసం అన్ని ప్రత్యేకమైన ఉప-శ్రేణి మొత్తాన్ని కనుగొనడానికి జావా కోడ్

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}
44

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

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

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

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

O (n ^ 2) (ఇక్కడ  “N” శ్రేణి యొక్క మూలకాల సంఖ్య. ఎందుకంటే చెత్త సందర్భంలో మనకు n ^ 2 వేర్వేరు ఉప-శ్రేణి మొత్తం ఉండవచ్చు.