දී ඇති මුදල සමඟ යුගල ගණන් කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇසොලයිට් ඇමේසන් ෆැක්ට්සෙට් ඉහළ දැමීම
අරා හැෂිං ගණිතය වර්ග කිරීම

ගැටලුවේදී “දී ඇති මුදල සමඟ යුගල ගණනය කරන්න” අපි පූර්ණ සංඛ්‍යාවක් ලබා දී ඇත අරාව[] සහ තවත් සංඛ්‍යාවක් 'එකතුව' යැයි කියනු ලැබේ, දී ඇති අරාවක ඇති මූලද්‍රව්‍ය දෙකෙන් ඕනෑම එකක් “එකතුවට” සමානද යන්න තීරණය කළ යුතුය.

උදාහරණයක්

ආදානය:

arr [] = 1,3,4,6,7 9} සහ sum = XNUMX.

ප්රතිදාන:

“ලබා දී ඇති මූලද්‍රව්‍ය sum ”සමාන වන '3' සහ '6' ඇති බැවින් '9' වෙත.

ආදානය:

arr [] = 11,3,5,7,10 20} සහ sum = XNUMX.

ප්රතිදාන:

'8' ට සමාන එකතුවක් නොමැති බැවින් "දී ඇති මුදල සමඟ මූලද්‍රව්‍ය හමු නොවේ".

ඇල්ගොරිතම

  1. කට්ටලයක්.
  2. 0 සිට 'i' දක්වා අරාවෙහි දිගට වඩා අඩුය.
    1. J යන්න sum-arr [i] ලෙස සකසන්න.
    2. කට්ටලයේ 'j' අඩංගු දැයි පරීක්ෂා කරන්න, සත්‍ය නම් j සහ arr [i] මුද්‍රණය කරන්න, මෙය යුගලය වේ.
    3. නැතහොත් කට්ටලයට ar [i] එකතු කරන්න.

පැහැදිලි කිරීම

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

අපගේ ප්‍රධාන අදහස වන්නේ හැෂ්සෙට් භාවිතා කිරීම සහ යුගලයක් සොයා ගැනීමයි. ඒ සඳහා අපි ගමන් කරන විට එකතුවෙහි වෙනස සහ අරාවෙහි එක් එක් අගය ගබඩා කිරීමට යන්නේ, මන්ද යත් යුගලයකට එම මූලද්‍රව්‍ය දෙක ඇති අතර දී ඇති එකතුවක් තවත් මූලද්‍රව්‍යයක් සොයා ගැනීම සඳහා යතුර වන හෙයින්, අපි සියලු අරාව මූලද්‍රව්‍ය කට්ටලයට ගබඩා කරමු. යුගලයේ එක් මූලද්‍රව්‍යයක් තිබේද නැද්ද යන්න සොයා බලන්න.

එය සොයා ගැනීම සඳහා, අපි හැෂිං ක්‍රමයක් භාවිතා කරමු.

අපි උදාහරණයක් ගනිමු:

arr [] = {1, 4, 45, 6, 10, 8};

  • i = 0, myset, sum = 16;

j = sum-arr [i];

එය j = 16-1 = 15 වන අතර නියත වශයෙන්ම 'j' සිතියමක නොපවතී.

එබැවින් එය my [1 'වන arr [i] එකතු කරයි.

  • i = 1, myset = {1}, sum = 16;

j = sum-arr [i];

එය j = 16-4 = 12 වන අතර නියත වශයෙන්ම 'j' සිතියමක නොමැත.

එබැවින් එය my [4 'වන arr [i] එකතු කරයි.

  • i = 2, myset = {1, 4}, sum = 16;

j = sum-arr [i];

එය j = 16-45 = -29 වන අතර නිසැකවම 'j' සිතියමක නොතිබෙනු ඇත.

එබැවින් එය my [45 'වන arr [i] එකතු කරයි.

  • i = 3, myset = {1, 4, 45}, sum = 16;

j = sum-arr [i];

එය j = 16-6 = 10 වන අතර j සිතියමක නොමැත.

එබැවින් එය my [6 'වන arr [i] එකතු කරයි.

  • i = 4, myset = {1, 4, 45, 6}, sum = 16;

j = sum-arr [i];

එනම් j = 16-10 = 6 වන අතර j සිතියමේ ඇත.

යුගලයේ තවත් අංගයක් අපට හමු වන්නේ මෙහිදීය. අපි දැනටමත් 16 සහ 10 දිනවල මෙහෙයුම් සිදු කර ඇත්තෙමු.

අපි මුද්‍රණය කරන්නේ:

“ලබා දී ඇති මුදල 16 ලෙස සොයාගත් මූලද්‍රව්‍ය (10, 6);

ඒ කියන්නේ මූලද්‍රව්‍ය දෙකක් අරාවෙහි ඇති අතර එය “එකතුවට” සමාන වේ.

ක්රියාත්මක කිරීම

ලබා දී ඇති මුදල සමඟ ගණන් යුගල සඳහා C ++ වැඩසටහන

#include <bits/stdc++.h>
using namespace std;

void getPairOfSum(int arr[], int arr_size, int sum)
{
    unordered_set<int> myset;
    for (int i = 0; i < arr_size; i++)
    {
        int j = sum - arr[i];
        if (myset.find(j) != myset.end())
        {
            cout << "Found elements with the given sum as "<<sum << " is (" << arr[i] <<", " << j << ")"<<endl;
        }
        myset.insert(arr[i]);
    }
}
int main()
{
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    getPairOfSum(arr, arr_size, sum);
    return 0;
}
Found elements with the given sum as 16 is (10, 6)

ලබා දී ඇති මුදල සමඟ ගණන් යුගල සඳහා ජාවා වැඩසටහන

import java.io.*;
import java.util.HashSet;

class twoElementSum {
  public static void getPairOfSum(int arr[], int sum) {
    HashSet<Integer> myset = new HashSet<Integer> ();
    for (int i = 0; i<arr.length; ++i) {
      int j = sum - arr[i];
      if (myset.contains(j)) {
        System.out.println("Found elements with the given sum as " + sum + " is (" + arr[i] + ", " + j + ")");
      }
      myset.add(arr[i]);
    }
  }
  public static void main(String[] args) {
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    getPairOfSum(arr, sum);
  }
}
Found elements with the given sum as 16 is (10, 6)

ලබා දී ඇති මුදල සමඟ ගණන් යුගල සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) මුළු අරාවම ගමන් කළ යුත්තේ එක් වරක් පමණි.

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

සාමාන්ය (n) අරා මූලද්‍රව්‍ය ගබඩා කිරීම සඳහා හැෂ් සිතියමක් භාවිතා කර ඇති බැවින්.

විමර්ශන