किसी दिए गए सरणी के लिए सभी अद्वितीय उप-सरणी योग का योग खोजें  


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Facebook ग्रेओरेन्ज सहज माइक्रोसॉफ्ट नगरो
ऐरे हैश छंटाई

मान लीजिए कि आपके पास एक पूर्णांक है। समस्या "किसी दिए गए सरणी के लिए सभी अद्वितीय उप-सरणी योग का योग ढूंढें" सभी अद्वितीय उप-सरणियों का योग खोजने के लिए कहती है (उप-सरणी योग प्रत्येक उप-सरणी के तत्वों का योग है)।

विशिष्ट उप-सरणी योग से हमारा तात्पर्य यह था कि किसी भी उप-सरणी का समान मूल्य नहीं है।

उदाहरण  

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

किसी दिए गए सरणी के लिए सभी अद्वितीय उप-सरणी योग का योग खोजें  

कलन विधि  

  1. डिक्लेयर ए नक्शा.
  2. सेट उत्पादन सेवा मेरे .
  3. सरणी को i = 0 से i तक ले जाएं
    1. ठीक योग 0 लिए.
    2. सरणी को j = i से j तक ले जाएं
      • योग में गिरफ्तारी [j] के मूल्य को जोड़ दें।
      • मानचित्र में योग और उसकी घटना जोड़ें।
  4. नक्शे को पीछे छोड़ें और उन प्रमुख प्रविष्टियों की जांच करें जिनका मूल्य 1 है।
    1. जब भी हम स्थिति को संतुष्ट पाते हैं, तब आउटपुट में कुंजियों का मूल्य जोड़ें।
  5. वापसी आउटपुट।

व्याख्या

हमें ए पूर्णांक सरणी। हमारा कार्य सभी अद्वितीय उप-सरणियों का योग ज्ञात करना है। प्रत्येक उप-सरणी का योग प्रत्येक उप-सरणी के तत्व का योग होगा। हम उपयोग करने जा रहे हैं हैशिंग इस सवाल को हल करने के लिए। जब भी हम i के मान को बदलते हैं, हम एक एरे के प्रत्येक तत्व को उठाते हुए, 0 पर आरम्भ करेंगे। जब हम आंतरिक पाश में प्रवेश करते हैं, तो हम एक सरणी से पार करेंगे i सेवा मेरे n, और सरणी और योग के प्रत्येक मूल्य को जोड़ना। फिर हम एक साथ मानचित्र में योग और उसकी घटना को संग्रहीत करते हैं। पूरे सरणी पर जाने के बाद, उप-सरणियों के सभी संभावित योगों का पता लगाएं। उसके बाद, हम नक्शे में उन रकमों की तलाश करते हैं जिनकी घटना केवल एक बार होती है। क्योंकि हम अद्वितीय उप-सरणियों का योग चाहते हैं, जिसका अर्थ अलग-अलग राशि है। इसलिए जब हम एक बार होने वाले नक्शे में राशि पाते हैं, तो कहने का मतलब है कि जिसकी आवृत्ति 1 है, हम उन रकमों के मूल्य को आउटपुट में जोड़ेंगे और अपडेट करेंगे।

यह भी देखें
सर्पिल रूप में स्तर के आदेश Traversal

इसके लिए एक उदाहरण मानते हुए:

उदाहरण

गिरफ्तार [] = {३, १, ४, ५}

सबसे पहले, हमारे पास 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 नेस्टेड लूप्स का उपयोग किया है और राशि की खोज ओ (1) में हाशप का उपयोग करके की गई है।

यह भी देखें
दी गई संख्या के बराबर उत्पाद के साथ ट्रिपल की संख्या की गणना करें

अंतरिक्ष जटिलता

O (n ^ 2) जहां "N" सरणी के तत्वों की संख्या है। क्योंकि सबसे खराब स्थिति में हमारे पास n ^ 2 अलग उप-सरणी योग हो सकते हैं।