පූර්ණ සංඛ්‍යා n සමූහයක ඇති සියලුම යුගලවලට වඩා f (a [i], a [j]) එකතුව


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ සිස්කෝ ෆේස්බුක් ඉහළ දැමීම Publicis Sapient
අරා හැෂ් ගණිතය

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. සිතියම සහ සකසන්න නිමැවුමකි 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]) එකතුවක් සොයා ගන්නේ එලෙසිනි.

අපි උදාහරණයක් සලකා බලමු:

උදාහරණයක්

Arr [] = {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) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. HashMap භාවිතය මඟින් සෙවීම / මකා දැමීම / ඇතුළු කිරීම සිදු කිරීමට අපට ඉඩ ලබා දේ ඕ (1). මේ අනුව පූර්ණ සංඛ්‍යා n කාණ්ඩයක ඇති සියලුම යුගලවලට වඩා f (a [i], a [j]) එකතුව සොයා ගැනීමේ කාල සංකීර්ණතාව රේඛීය ලෙස අඩු වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. අපට HashMap හි යතුරු n ඇතුළු කිරීමට සිදුවිය හැකි බැවින් අවකාශයේ සංකීර්ණතාව රේඛීය වේ.