दिलेल्या अ‍ॅरेसाठी सर्व अद्वितीय उप-अ‍ॅरेची बेरीज शोधा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन फेसबुक ग्रेऑरेंज अंतर्ज्ञानाने जाणणे मायक्रोसॉफ्ट नागररो
अरे हॅश वर्गीकरण

समजा आपल्याकडे पूर्णांक संख्या आहे. “दिलेल्या अ‍ॅरेसाठी सर्व अद्वितीय उप-अ‍ॅरेची बेरीज शोधा” ही समस्या सर्व अद्वितीय उप-अ‍ॅरेची बेरीज शोधण्यासाठी विचारते (उप-अ‍ॅरे बेरीज प्रत्येक उप-अ‍ॅरेच्या घटकांची बेरीज आहे).

अनन्य उप-अ‍ॅरेची बेरीज करून, आमचे म्हणणे असे होते की कोणत्याही उप-अ‍ॅरेचे मूल्य समान नाही.

उदाहरण

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

दिलेल्या अ‍ॅरेसाठी सर्व अद्वितीय उप-अ‍ॅरेची बेरीज शोधा

अल्गोरिदम

  1. घोषित ए नकाशा.
  2. सेट करा आउटपुट ते 0.
  3. अ‍ॅरे i = 0 ते i पर्यंत जा
    1. सेट करा बेरीज 0 पर्यंत.
    2. J = i, j पासून अ‍ॅरेचा आढावा घ्या
      • बेरीजमध्ये अररचे मूल्य [j] जोडा.
      • नकाशामध्ये बेरीज आणि त्याची घटना जोडा.
  4. नकाशा ओलांडून त्या कीच्या नोंदी तपासा ज्यांचे मूल्य 1 आहे.
    1. जेव्हा आम्हाला कंडिशन समाधानी वाटेल तेव्हा आउटपुटमध्ये कीचे मूल्य जोडा.
  5. रिटर्न आउटपुट

स्पष्टीकरण

आम्हाला एक दिले जाते पूर्णांक अॅरे. आमचे कार्य म्हणजे सर्व अनन्य उप-अ‍ॅरेची बेरीज शोधणे. प्रत्येक उप-अ‍ॅरेची बेरीज प्रत्येक उप-अ‍ॅरेच्या घटकाची बेरीज असेल. आम्ही वापरणार आहोत हॅशिंग हा प्रश्न सोडविण्यासाठी. जेव्हा आम्ही i ची व्हॅल्यू बदलतो तेव्हा 0 ने प्रारंभ करून अ‍ॅरेची प्रत्येक घटक निवडत आहोत. जेव्हा आपण अंतर्गत लूपमध्ये प्रवेश करतो, तेव्हा आपण अ‍ॅरे वरून जाईल i ते n, आणि अ‍ॅरे आणि बेरीजचे प्रत्येक मूल्य जोडून. मग आम्ही एकाच वेळी बेरीज आणि त्याची घटना नकाशामध्ये संचयित करतो. संपूर्ण अ‍ॅरेला भेट दिल्यानंतर, उप-अ‍ॅरेची सर्व संभाव्य बेरीज शोधा. त्यानंतर, आम्ही नकाशामध्ये अशा रकमेसाठी शोधतो ज्यांची घटना फक्त एकदाच आहे. कारण आम्हाला अद्वितीय उप-अ‍ॅरेची बेरीज हवी आहे, ज्याचा अर्थ वेगळा आहे. जेव्हा आपल्याला नकाशामध्ये एकदाची बेरीज आढळली, ज्याची वारंवारता 1 आहे म्हणजे सांगायचे तर आम्ही त्या रकमेचे मूल्य आउटपुटमध्ये जोडू आणि अद्यतनित करू.

त्यासाठी एक उदाहरण विचारात घेताः

उदाहरण

अरे [] = {3, 1, 4, 5}

प्रथम, आपल्याकडे i = 0 आहे, नंतर आपल्याकडे घटक म्हणून 3 आहेत आणि आपण 3 पासून प्रारंभ करू, आम्ही बेरीजमध्ये 3 जोडणार आहोत आणि 3 नकाशामध्ये अद्यतनित करू, नंतर बेरीजमध्ये 1 जोडू आणि 4 नकाशामध्ये अद्यतनित करू. , नंतर बेरीजमध्ये घटक म्हणून 4 घ्या आणि नकाशामध्ये 7 जोडा. अशाप्रकारे, 5 भेट देऊन आणि नकाशामध्ये 12 अद्यतनित केल्यावर आम्ही प्रथम ट्रॅव्हर्झल समाप्त करू.

जेव्हा आपण 4 म्हणून घटक म्हणून घेतो आणि 4 पासून प्रारंभ करतो तेव्हा आम्ही नकाशात बेरीज करू, कारण 4 आधीच अस्तित्वात आहे नकाशा, आम्ही फक्त त्याची वारंवारता वाढवू, आणि ज्यांची वारंवारता 1 नाही अशा रकमेकडे दुर्लक्ष करू. अशा प्रकारे, आम्ही अद्वितीय उप-अ‍ॅरे हाताळू शकू.

कोड

दिलेल्या अ‍ॅरेसाठी सर्व अद्वितीय उप-अ‍ॅरेची बेरीज शोधण्यासाठी सी ++ कोड

#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जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. कारण आम्ही 2 नेस्टेड लूप वापरलेले आहेत आणि हॅशमॅप वापरुन बेरीज (ओ) मध्ये बेरीज शोधणे आहे.

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

ओ (एन ^ 2) जेथे “एन” अ‍ॅरेच्या घटकांची संख्या आहे. कारण सर्वात वाईट परिस्थितीत आपल्याकडे n ^ 2 भिन्न उप-अ‍ॅरेची बेरीज असू शकतात.