N పూర్ణాంకాల శ్రేణిలోని అన్ని జతలపై f (a [i], a [j]) మొత్తం


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

1 <= i <j <= n మనకు అందించబడినట్లు పరిగణనలోకి తీసుకునే విధంగా n పూర్ణాంకాల శ్రేణిలోని అన్ని జతలపై f (a [i], a [j]) మొత్తాన్ని తెలుసుకోవడానికి సమస్య ప్రకటన అడుగుతుంది. పూర్ణాంకాల శ్రేణి.

N పూర్ణాంకాల శ్రేణిలోని అన్ని జతలపై f (a [i], a [j]) మొత్తం

ఉదాహరణ

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

వివరణ

జత 3,1 మరియు 3,1 జతలు మాత్రమే.

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

వివరణ

ఇక్కడ కూడా, రెండు జతల (1, 3) ఉన్నాయి.

అల్గారిథం

  1. ప్రకటించండి a చిహ్నం మరియు సెట్ అవుట్పుట్ నుండి 0 మరియు చెక్సమ్ 0 కు.
  2. నుండి ప్రారంభమయ్యే శ్రేణిని దాటండి i = 0 కు i = n,
    1. అవుట్పుట్ చేయండి + = (i * a [i]) - చెక్సమ్ మరియు చెక్సమ్ + = a [i];
    2. మ్యాప్‌లో [i] -1 ఒక కీగా ఉందో లేదో తనిఖీ చేయండి.
      1. నిజమైతే, మ్యాప్ యొక్క [i] -1 విలువను అవుట్‌పుట్‌లోకి చేర్చడం ద్వారా అవుట్‌పుట్‌ను నవీకరించండి.
      2. మ్యాప్‌లో [i] +1 కీగా ఉందో లేదో తనిఖీ చేయండి. నిజమైతే, మ్యాప్ యొక్క [i] +1 విలువను అవుట్పుట్‌లో చేర్చడం ద్వారా అవుట్‌పుట్‌ను నవీకరించండి.
    3. షరతులు ఏవీ సంతృప్తి చెందకపోతే, శ్రేణి మూలకం యొక్క ఫ్రీక్వెన్సీని మ్యాప్‌లో లెక్కించండి మరియు నిల్వ చేయండి.
  3. రిటర్న్ అవుట్పుట్.

వివరణ

మాకు ఒక వచ్చింది అమరిక పూర్ణ సంఖ్య, పైన పేర్కొన్న పరిస్థితిని సంతృప్తిపరిచే శ్రేణిలో ఉన్న అన్ని జతల మొత్తాన్ని కనుగొనడం మా పని. జతలు ఏవీ ఇచ్చిన పరిస్థితిని సంతృప్తిపరచకపోతే, మనం 0 తిరిగి ఇస్తాము. దీనిని పరిష్కరించడానికి మనం a మ్యాప్ మరియు ఏకకాలంలో ప్రతి శ్రేణి మూలకంపై అన్ని ఆపరేషన్లు చేయడం మరియు మా అవుట్‌పుట్‌ను నవీకరించడం మరియు మా మ్యాప్‌లో తనిఖీ చేయడం. మేము మా నిజమైన అవుట్‌పుట్‌పై నిఘా ఉంచే అదనపు వేరియబుల్‌ను తీసుకోబోతున్నాం, దాన్ని చెక్‌సమ్ అని పిలుస్తాము. మేము అవుట్పుట్ మరియు చెక్సమ్ను 0 కి సెట్ చేస్తాము. మరియు n పూర్ణాంకాల శ్రేణిలో అన్ని జతలపై f (a [i], a [j]) మొత్తాన్ని ఎలా కనుగొంటాము.

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

ఉదాహరణ

అర్ [] = {1, 2, 3, 1, 3}, అవుట్‌పుట్: 0, చెక్‌సమ్: 0

  • మేము 0 వ ఇండెక్స్ ఎలిమెంట్‌ను ఎంచుకుని, ఆపై దాని ఇండెక్స్ ద్వారా గుణించి, చెక్‌సమ్‌ను తీసివేసి, దాన్ని అవుట్‌పుట్‌లో చేర్చుతాము, మనకు వచ్చింది

అవుట్పుట్: 0, చెక్సమ్: 1

మ్యాప్ {1 = 1}, ఏదైనా షరతు సంతృప్తి చెందదు, కాబట్టి మేము విలువను మ్యాప్‌లో చేర్చుతాము.

  • 1 కోసంst ఇండెక్స్ ఎలిమెంట్, అదే ఆపరేషన్ చేయండి, కానీ ఈసారి, ఇది మొదటి ఇఫ్ స్టేట్మెంట్ యొక్క పరిస్థితిని సంతృప్తిపరుస్తుంది మరియు నవీకరించబడిన అవుట్పుట్ పొందిన తరువాత, మనకు లభిస్తుంది.

నవీకరించబడిన అవుట్పుట్: 0, చెక్సమ్: 3

మ్యాప్ {1 = 1, 2 = 1}, ఈసారి కూడా మేము ఆ విలువను మ్యాప్‌లోకి చేర్చాము.

  • 2 కోసంnd మూలకం, మునుపటిలాగే అదే ఆపరేషన్, ఈసారి అది మూలకాన్ని [i] -1 ను కనుగొంటుంది మరియు మనకు నవీకరించబడిన అవుట్పుట్ వచ్చింది:

నవీకరించబడిన అవుట్పుట్: 2, చెక్సమ్: 6

మ్యాప్ {1 = 1, 2 = 1, 3 = 1}, మూలకం మరియు దాని పౌన .పున్యాన్ని జోడిస్తుంది.

  • 3 వ మూలకం కోసం, ఇది రెండవ స్టేట్మెంట్‌ను సంతృప్తిపరుస్తుంది, అంటే మ్యాప్‌లో [i] +1 విలువ ఉంటే అది అనుసరిస్తుంది, అప్పుడు మేము నవీకరించిన అవుట్‌పుట్ పొందిన తర్వాత:

నవీకరించబడిన అవుట్పుట్: 0, చెక్సమ్: 7, మ్యాప్: {1 = 2, 2 = 1, 3 = 1}

  • 4 వ మూలకం కోసం, మొదటి if స్టేట్మెంట్ దాటిన తరువాత.

నవీకరించబడిన అవుట్పుట్: 4, చెక్సమ్: 10

మ్యాప్ {1 = 2, 2 = 1, 3 = 2}

మరియు మేము అవుట్పుట్ను తిరిగి ఇస్తాము: 4

కోడ్

N పూర్ణాంకాల శ్రేణిలో అన్ని జతలపై f (a [i], a [j]) మొత్తాన్ని కనుగొనడానికి C ++ కోడ్

#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

N పూర్ణాంకాల శ్రేణిలో అన్ని జతలపై 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

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

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

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. హాష్ మ్యాప్ యొక్క ఉపయోగం శోధన / తొలగింపు / చొప్పించడం నిర్వహించడానికి అనుమతిస్తుంది O (1). అందువల్ల n పూర్ణాంకాల శ్రేణిలోని అన్ని జతలపై f (a [i], a [j]) మొత్తాన్ని కనుగొనే సమయ సంక్లిష్టత సరళంగా తగ్గించబడుతుంది.

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

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. మేము హాష్ మ్యాప్‌లో n కీలను చొప్పించవలసి ఉంటుంది కాబట్టి, స్థల సంక్లిష్టత సరళంగా ఉంటుంది.