N પૂર્ણાંકોની એરેમાં બધા જોડીઓ ઉપર f (a [i], a [j]) નો સરવાળો


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે સિસ્કો ફેસબુક પર્યટન પબ્લિકિસ સેપિયન્ટ
અરે હેશ મઠ

સમસ્યાનું નિવેદન એ એન પૂર્ણાંકોની એરેમાં તમામ જોડી ઉપર એવી રીતે એફ (એ [i], એ [જે]) નો સરવાળો શોધવા માટે પૂછે છે કે 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. થી શરૂ થતા એરેને પસાર કરો હું = 0 થી i = n,
    1. આઉટપુટ કરો + = (હું * એ [i]) - ચેકસમ અને ચેકસમ + = એ [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 અનુક્રમણિકા તત્વ, સમાન કામગીરી કરો, પરંતુ આ સમયે, તે પ્રથમ if સ્ટેટમેંટની સ્થિતિને પૂર્ણ કરશે, અને અપડેટ આઉટપુટ મળ્યા પછી, આપણે મેળવીશું.

અપડેટ કરેલ આઉટપુટ: 0, ચેકસમ: 3

નકશો {1 = 1, 2 = 1}, આ સમયે પણ અમે નકશામાં તેની ઘટના સાથે મૂલ્ય ઉમેરીએ છીએ.

  • 2 માટેnd તત્વ, સમાન કામગીરી પહેલાની જેમ થઈ, આ વખતે તે તત્વ શોધી કા aે છે [i] -1 અને અમને અપડેટ આઉટપુટ મળ્યું:

અપડેટ કરેલ આઉટપુટ: 2, ચેકસમ: 6

નકશા {1 = 1, 2 = 1, 3 = 1}, તત્વ અને તેની આવર્તન ઉમેરીને.

  • 3 જી તત્વ માટે, તે બીજાને જો નિવેદનને સંતોષે છે, તેનો અર્થ એ છે કે જો નકશામાં મૂલ્ય એ [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

જાવા કોડ એફ પૂર્ણાંકોની એરેમાં તમામ જોડીઓ પર એફ (એ [i], એ [જે]) નો સરવાળો શોધવા માટે

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. હેશમેપનો ઉપયોગ અમને શોધ / કાtionી નાખવા / દાખલ કરવા માટે પરવાનગી આપે છે ઓ (1). આમ n પૂર્ણાંકોની એરેમાં તમામ જોડીઓ પર f (a [i], a [j]) નો સરવાળો શોધવા માટેની સમયની જટિલતા ઘટાડીને રેખીય કરવામાં આવે છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. આપણે હેશમેપમાં એન કીઓ દાખલ કરવી પડી શકે છે, તેથી આ જગ્યા જટિલતા રેખીય છે.