N முழு எண்களின் வரிசையில் அனைத்து ஜோடிகளுக்கும் மேலாக f (a [i], a [j]) தொகை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது சிஸ்கோ பேஸ்புக் உயர்வு பப்ளிஸ் சப்பியண்ட்
அணி ஹாஷ் கணித

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. ஒரு அறிவிக்கவும் வரைபடம் மற்றும் அமைக்கவும் வெளியீடு to 0 மற்றும் செக்சம் 0 வரை.
  2. தொடங்கும் வரிசையை கடந்து செல்லுங்கள் நான் = 0 க்கு i = n,
    1. வெளியீடு + = (i * a [i]) - செக்சம் மற்றும் செக்சம் + = a [i];
    2. வரைபடத்தில் ஒரு விசையாக [i] -1 இருக்கிறதா என்று சோதிக்கவும்.
      1. உண்மை எனில், வரைபடத்தின் [i] -1 இன் மதிப்பை வெளியீட்டில் சேர்ப்பதன் மூலம் வெளியீட்டைப் புதுப்பிக்கவும்.
      2. வரைபடத்தில் ஒரு விசையாக [i] +1 இருக்கிறதா என்று சோதிக்கவும். உண்மை எனில், வரைபடத்தின் [i] +1 இன் மதிப்பை வெளியீட்டில் சேர்ப்பதன் மூலம் வெளியீட்டைப் புதுப்பிக்கவும்.
    3. நிபந்தனை எதுவும் திருப்தி அடையவில்லை என்றால், வரிசை உறுப்புகளின் அதிர்வெண்ணை வரைபடத்தில் எண்ணி சேமிக்கவும்.
  3. வெளியீடு திரும்பவும்.

விளக்கம்

எங்களுக்கு ஒரு கிடைத்தது வரிசை முழு, எங்கள் பணி மேலே உள்ள நிலையை பூர்த்தி செய்யும் ஒரு வரிசையில் இருக்கும் அனைத்து ஜோடிகளின் கூட்டுத்தொகையைக் கண்டுபிடிப்பதாகும். ஜோடிகளில் எதுவும் கொடுக்கப்பட்ட நிபந்தனையை பூர்த்தி செய்யாவிட்டால், நாங்கள் 0 ஐத் தருகிறோம். இதைத் தீர்க்க நாம் ஒரு பயன்படுத்துவோம் வரைபடம் ஒரே நேரத்தில் ஒவ்வொரு வரிசை உறுப்புகளிலும் அனைத்து செயல்பாடுகளையும் செய்து எங்கள் வெளியீட்டைப் புதுப்பித்து எங்கள் வரைபடத்தையும் சரிபார்க்கவும். எங்கள் உண்மையான வெளியீட்டைக் கண்காணிக்கும் கூடுதல் மாறியை நாங்கள் எடுக்கப் போகிறோம், அதை ஒரு செக்சம் என்று அழைக்கலாம். வெளியீடு மற்றும் செக்சம் 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]) தொகையைக் கண்டுபிடிக்க சி ++ குறியீடு

#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) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. HashMap இன் பயன்பாடு தேடல் / நீக்குதல் / செருகலைச் செய்ய அனுமதிக்கிறது ஓ (1). இதனால் n முழு எண்களின் வரிசையில் அனைத்து ஜோடிகளுக்கும் மேலாக f (a [i], a [j]) தொகையைக் கண்டுபிடிப்பதற்கான நேர சிக்கலானது நேரியல் ஆக குறைக்கப்படுகிறது.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. நாம் ஹாஷ்மேப்பில் n விசைகளைச் செருக வேண்டியிருக்கும் என்பதால், விண்வெளி சிக்கலானது நேரியல்.