एन पूर्णांकांच्या अ‍ॅरेमधील सर्व जोड्यांकरिता एफ (ए [मी], ए [जे]) ची बेरीज


अडचण पातळी सोपे
वारंवार विचारले सिस्को फेसबुक वाढ पब्लिसिस सेपिएंट
अरे हॅश गणित

समस्या स्टेटमेंटमध्ये एन (पूर्णांक) च्या अ‍ॅरेमधील सर्व जोड्यांवरील एफ (ए [i], ए [जे]) ची बेरीज अशा प्रकारे जाणून घेण्यास सांगितले जाते की 1 <= i <j <= n आम्हाला प्रदान करण्यात आले आहे याचा विचार करुन पूर्णांकांची अ‍ॅरे.

एन पूर्णांकांच्या अ‍ॅरेमधील सर्व जोड्यांकरिता एफ (ए [मी], ए [जे]) ची बेरीज

उदाहरण

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

स्पष्टीकरण

केवळ 3,1 आणि 3,1 जोड्या.

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

स्पष्टीकरण

येथे देखील, (1, 3) च्या दोन जोड्या आहेत.

अल्गोरिदम

  1. घोषित ए नकाशा आणि सेट आउटपुट 0 आणि चेकसम 0 पर्यंत.
  2. सुरू होणार्‍या अ‍ॅरेचा आढावा घ्या i = 0 ते i = n,
    1. आउटपुट करा + = (i * अ [i]) - चेकसम आणि चेकसम + = अ [आय];
    2. नकाशामध्ये एक [i] -1 की म्हणून उपस्थित आहे की नाही ते तपासा.
      1. खरे असल्यास, आउटपुटमध्ये नकाशाची [i] -1 चे मूल्य जोडून आउटपुट अद्यतनित करा.
      2. नकाशामध्ये एक [i] +1 की म्हणून उपस्थित आहे की नाही ते तपासा. खरे असल्यास, आउटपुटमध्ये नकाशाची [i] +1 चे मूल्य जोडून आउटपुट अद्यतनित करा.
    3. जर कोणतीही अट पूर्ण होत नसेल तर अ‍ॅरे एलिमेंटची वारंवारिता नकाशामध्ये मोजा आणि संचयित करा.
  3. रिटर्न आउटपुट

स्पष्टीकरण

आम्ही एक आला अॅरे पूर्णांक, आमचे कार्य वरील अटीस पूर्ण करणारे अ‍ॅरेमध्ये असलेल्या सर्व जोड्यांची बेरीज शोधणे आहे. जर जोड्यांपैकी कोणतीही एक दिलेली अट पूर्ण करीत नसेल तर आम्ही फक्त 0 परत करतो. हे सोडवण्यासाठी आपण a वापरू नकाशा आणि एकाच वेळी प्रत्येक अ‍ॅरे घटकांवर सर्व ऑपरेशन्स करत आहोत आणि आपले आउटपुट अपडेट करत आहोत आणि आमच्या नकाशावर देखील तपासत आहोत. आम्ही एक अतिरिक्त व्हेरिएबल घेणार आहोत जे आपल्या वास्तविक आउटपुटवर लक्ष ठेवेल, आम्ही त्याला चेकसमधे कॉल करू. आउटपुट आणि चेकसम 0 वर सेट करू. आणि अशाप्रकारे एन (पूर्णांक) असलेल्या अ‍ॅरे मधील सर्व जोड्यांमधे f (a [i], a [j]) ची बेरीज कशी आढळेल.

चला त्याचं उदाहरण घेऊ:

उदाहरण

अरे [] = {1, 2, 3, 1, 3}, आउटपुट: 0, चेकसम: 0

  • आपण 0 व्या अनुक्रमणिकेचा घटक निवडू आणि नंतर सुरू करू आणि नंतर त्याच्या अनुक्रमणिकेद्वारे गुणाकार करू आणि चेकसम वजा करू आणि नंतर आउटपुटमध्ये जोडू,

आउटपुट: 0, चेकसम: 1

नकाशा {1 = 1}, कोणतीही अट पूर्ण करीत नाही, म्हणून आम्ही नकाशामध्ये मूल्य जोडतो.

  • 1 साठीst इंडेक्स एलिमेंट, तेच ऑपरेशन करा, परंतु या वेळी हे प्रथम if स्टेटमेंटची अट पूर्ण करेल, आणि अपडेट केलेले आउटपुट मिळाल्यावर आपल्याला मिळेल.

अद्यतनित आउटपुट: 0, चेकसम: 3

नकाशा {1 = 1, 2 = 1}, यावेळी आम्ही नकाशामध्ये त्याच्या घटनेसह मूल्य जोडतो.

  • 2 साठीnd घटक, पूर्वीप्रमाणेच ऑपरेशन केले, यावेळी तो घटक [i] -1 हा घटक सापडला आणि आपल्याला अद्ययावत आउटपुट मिळाले:

अद्यतनित आउटपुट: 2, चेकसम: 6

घटक आणि त्याची वारंवारता जोडून map 1 = 1, 2 = 1, 3 = 1 map नकाशा.

  • 3rd थ्या घटकासाठी ते दुसर्‍या if स्टेटमेंटचे समाधान करते, म्हणजेच नकाशामध्ये a [i] +1 मूल्य असेल तर ते आपल्यास अद्ययावत आउटपुट मिळाल्यानंतर मिळते:

अद्यतनित आउटपुट: 0, चेकसम: 7, नकाशा: {1 = 2, 2 = 1, 3 = 1}

  • चौथ्या घटकासाठी पहिले स्टेटमेंट पास केल्यावर.

अद्यतनित आउटपुट: 4, चेकसम: 10

नकाशा {1 = 2, 2 = 1, 3 = 2}

आणि आऊटपुट परत करू: 4

कोड

एन पूर्णांकांमधील अ‍ॅरेमधील सर्व जोड्यांकरिता एफ (अ [i], ए [जे]) ची बेरीज शोधण्यासाठी सी ++ कोड

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}
4

एन पूर्णांकाच्या अ‍ॅरेमधील सर्व जोड्यांवरील f (a [i], a [j]) ची बेरीज शोधण्यासाठी जावा कोड

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}
4

गुंतागुंत विश्लेषण

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. हॅशमॅपचा वापर आम्हाला शोध / हटविणे / अंतर्भूत करण्याची परवानगी देतो ओ (1). अशाप्रकारे एन (पूर्णांक) च्या अ‍ॅरेमधील सर्व जोड्यांवरील f (a [i], a [j]) ची बेरीज शोधण्याची वेळ गुंतागुंत कमी करते.

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

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्हाला हॅशमॅपमध्ये एन की घालाव्या लागतील, म्हणून स्पेस कॉम्प्लेक्सिटी रेषात्मक आहे.