N സംഖ്യകളുടെ ഒരു നിരയിലെ എല്ലാ ജോഡികളിലും f (a [i], a [j]) ആകെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു സിസ്കോ ഫേസ്ബുക്ക് ഉയർത്തൽ പബ്ലിസിസ് സാപിയന്റ്
അറേ ഹാഷ് മഠം

പ്രശ്ന സംഖ്യ n സംഖ്യകളുടെ ഒരു നിരയിലെ എല്ലാ ജോഡികൾക്കും മുകളിലുള്ള f (a [i], a [j]) തുക കണ്ടെത്താൻ ആവശ്യപ്പെടുന്നു, അങ്ങനെ 1 <= i <j <= n പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര.

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. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം സജ്ജമാക്കുക ഔട്ട്പുട്ട് മുതൽ 0 വരെ ചെക്ക്സം 0 ലേക്ക്.
  2. ആരംഭിക്കുന്ന ശ്രേണിയിലൂടെ സഞ്ചരിക്കുക i = 0 ലേക്ക് i = n,
    1. Output ട്ട്‌പുട്ട് ചെയ്യുക + = (i * a [i]) - ചെക്ക്‌സം, ചെക്ക്സം + = a [i];
    2. മാപ്പിൽ ഒരു [i] -1 ഒരു കീയായി ഉണ്ടോയെന്ന് പരിശോധിക്കുക.
      1. ശരിയാണെങ്കിൽ, മാപ്പിന്റെ [i] -1 ന്റെ മൂല്യം .ട്ട്‌പുട്ടിൽ ചേർത്ത് output ട്ട്‌പുട്ട് അപ്‌ഡേറ്റുചെയ്യുക.
      2. മാപ്പിൽ ഒരു [i] +1 ഒരു കീയായി ഉണ്ടോയെന്ന് പരിശോധിക്കുക. ശരിയാണെങ്കിൽ, .ട്ട്‌പുട്ടിലേക്ക് മാപ്പിന്റെ [i] +1 ന്റെ മൂല്യം ചേർത്ത് അപ്‌ഡേറ്റ് അപ്‌ഡേറ്റുചെയ്യുക.
    3. നിബന്ധനകളൊന്നും തൃപ്തികരമല്ലെങ്കിൽ, അറേ ഘടകത്തിന്റെ ആവൃത്തി മാപ്പിൽ കണക്കാക്കി സംഭരിക്കുക.
  3. Return ട്ട്‌പുട്ട് നൽകുന്നു.

വിശദീകരണം

ഞങ്ങൾക്ക് ഒരു ലഭിച്ചു ശ്രേണി പൂർണ്ണസംഖ്യ, മുകളിലുള്ള അവസ്ഥയെ തൃപ്തിപ്പെടുത്തുന്ന ഒരു അറേയിൽ നിലവിലുള്ള എല്ലാ ജോഡികളുടെയും തുക കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ജോഡികളൊന്നും തന്നിരിക്കുന്ന അവസ്ഥയെ തൃപ്തിപ്പെടുത്തിയില്ലെങ്കിൽ ഞങ്ങൾ 0 നൽകുന്നു. ഇത് പരിഹരിക്കാൻ ഞങ്ങൾ a ഉപയോഗിക്കും ഭൂപടം അതോടൊപ്പം ഓരോ അറേ ഘടകത്തിലും എല്ലാ പ്രവർത്തനങ്ങളും നടത്തുകയും output ട്ട്‌പുട്ട് അപ്‌ഡേറ്റുചെയ്യുകയും മാപ്പിൽ പരിശോധിക്കുകയും ചെയ്യുന്നു. ഞങ്ങളുടെ യഥാർത്ഥ output ട്ട്‌പുട്ടിനെ നിരീക്ഷിക്കുന്ന ഒരു അധിക വേരിയബിൾ ഞങ്ങൾ എടുക്കാൻ പോകുന്നു, നമുക്ക് ഇതിനെ ഒരു ചെക്ക്സം എന്ന് വിളിക്കാം. Output ട്ട്‌പുട്ടും ചെക്ക്‌സവും 0 ആയി സജ്ജീകരിക്കും. അങ്ങനെയാണ് എല്ലാ ജോഡികളിലും n സംഖ്യകളുടെ ഒരു നിരയിൽ f (a [i], a [j]) കണ്ടെത്തുന്നത്.

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

Arr [] = {1, 2, 3, 1, 3}, put ട്ട്‌പുട്ട്: 0, ചെക്ക്‌സം: 0

  • ഞങ്ങൾ 0-ാമത്തെ സൂചിക ഘടകം തിരഞ്ഞെടുത്ത് അതിന്റെ സൂചിക കൊണ്ട് ഗുണിക്കുകയും ചെക്ക്സം കുറയ്ക്കുകയും output ട്ട്‌പുട്ടിൽ ചേർക്കുകയും ചെയ്യും

Put ട്ട്‌പുട്ട്: 0, ചെക്ക്‌സം: 1

മാപ്പ് {1 = 1}, ഏതെങ്കിലും അവസ്ഥ തൃപ്തികരമല്ല, അതിനാൽ ഞങ്ങൾ മാപ്പിൽ മൂല്യം ചേർക്കുന്നു.

  • 1- നായിst സൂചിക ഘടകം, സമാന പ്രവർത്തനം നടത്തുക, എന്നാൽ ഇത്തവണ അത് ആദ്യത്തെ if സ്റ്റേറ്റ്മെന്റിന്റെ അവസ്ഥയെ തൃപ്തിപ്പെടുത്തും, കൂടാതെ അപ്‌ഡേറ്റ് ചെയ്ത output ട്ട്‌പുട്ട് ലഭിച്ചതിന് ശേഷം ഞങ്ങൾക്ക് ലഭിക്കും.

അപ്‌ഡേറ്റുചെയ്‌ത put ട്ട്‌പുട്ട്: 0, ചെക്ക്‌സം: 3

മാപ്പ് {1 = 1, 2 = 1}, ഈ സമയം മാപ്പിലേക്ക് ആ മൂല്യം കൂടി ചേർക്കുന്നു.

  • 2- നായിnd ഘടകം, മുമ്പത്തെപ്പോലെ തന്നെ പ്രവർത്തനം, ഇത്തവണ അത് [i] -1 എന്ന ഘടകം കണ്ടെത്തുകയും ഞങ്ങൾക്ക് അപ്‌ഡേറ്റ് output ട്ട്‌പുട്ട് ലഭിക്കുകയും ചെയ്തു:

അപ്‌ഡേറ്റുചെയ്‌ത put ട്ട്‌പുട്ട്: 2, ചെക്ക്‌സം: 6

മാപ്പ് {1 = 1, 2 = 1, 3 = 1}, ഘടകവും അതിന്റെ ആവൃത്തിയും ചേർക്കുന്നു.

  • മൂന്നാമത്തെ ഘടകത്തിന്, ഇത് രണ്ടാമത്തെ if സ്റ്റേറ്റ്മെന്റിനെ തൃപ്തിപ്പെടുത്തുന്നു, അതിനർത്ഥം മാപ്പിൽ ഒരു [i] +3 മൂല്യം അടങ്ങിയിട്ടുണ്ടെങ്കിൽ അത് പിന്തുടരുന്നു എന്നാണ്, തുടർന്ന് അപ്‌ഡേറ്റ് ചെയ്ത output ട്ട്‌പുട്ട് ലഭിച്ച ശേഷം:

അപ്‌ഡേറ്റുചെയ്‌ത put ട്ട്‌പുട്ട്: 0, ചെക്ക്‌സം: 7, മാപ്പ്: {1 = 2, 2 = 1, 3 = 1}

  • നാലാമത്തെ ഘടകത്തിന്, ആദ്യ if സ്റ്റേറ്റ്മെന്റ് നൽകിയ ശേഷം.

അപ്‌ഡേറ്റുചെയ്‌ത put ട്ട്‌പുട്ട്: 4, ചെക്ക്‌സം: 10

മാപ്പ് {1 = 2, 2 = 1, 3 = 2}

ഞങ്ങൾ put ട്ട്‌പുട്ട് നൽകും: 4

കോഡ്

N സംഖ്യകളുടെ ഒരു നിരയിലെ എല്ലാ ജോഡികളിലും f (a [i], a [j]) തുക കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. തിരയൽ / ഇല്ലാതാക്കൽ / ഉൾപ്പെടുത്തൽ നടത്താൻ ഹാഷ്‌മാപ്പിന്റെ ഉപയോഗം ഞങ്ങളെ അനുവദിക്കുന്നു O (1). N സംഖ്യകളുടെ ഒരു നിരയിലെ എല്ലാ ജോഡികളിലും f (a [i], a [j]) തുക കണ്ടെത്തുന്നതിനുള്ള സമയ സങ്കീർണ്ണത രേഖീയമായി ചുരുങ്ങുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. നമുക്ക് ഹാഷ്മാപ്പിൽ n കീകൾ ചേർക്കേണ്ടിവരാം, അതിനാൽ സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.