നൽകിയ തുകയ്‌ക്കൊപ്പം ജോഡി എണ്ണുക


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

“നൽകിയ സംഖ്യയുമായി ജോഡി എണ്ണുക” എന്ന പ്രശ്‌നത്തിൽ ഞങ്ങൾ ഒരു സംഖ്യ നൽകി ശ്രേണി[] മറ്റൊരു സംഖ്യ 'സം' എന്ന് പറയുന്നു, തന്നിരിക്കുന്ന അറേയിലെ രണ്ട് ഘടകങ്ങളിൽ ഏതെങ്കിലും ഒന്നിന് “തുക” എന്നതിന് തുല്യമായ തുക ഉണ്ടോ എന്ന് നിങ്ങൾ നിർണ്ണയിക്കണം.

ഉദാഹരണം

ഇൻപുട്ട്:

arr [] = 1,3,4,6,7 9}, തുക = XNUMX.

ഔട്ട്പുട്ട്:

“നൽകിയിരിക്കുന്ന ഘടകങ്ങൾ കണ്ടെത്തി sum ”എന്നത് തുല്യമായ '3', '6' എന്നിവ ഉള്ളതിനാൽ '9' ലേക്ക്.

ഇൻപുട്ട്:

arr [] = 11,3,5,7,10 20}, തുക = XNUMX.

ഔട്ട്പുട്ട്:

'8' ന് തുല്യമായ സംഖ്യകളൊന്നും ഇല്ലാത്തതിനാൽ “തന്നിരിക്കുന്ന തുകയ്‌ക്കൊപ്പം ഘടകങ്ങൾ കണ്ടെത്തിയില്ല”.

അൽഗോരിതം

  1. ഒരു പ്രഖ്യാപിക്കുക ഗണം.
  2. 0 മുതൽ 'i' വരെ അറേയുടെ നീളത്തേക്കാൾ കുറവാണ്.
    1. J- നെ സം-അറയിലേക്ക് സജ്ജമാക്കുക [i].
    2. സെറ്റിൽ 'j' ഉണ്ടോയെന്ന് പരിശോധിക്കുക, true ആണെങ്കിൽ j, arr [i] എന്നിവ പ്രിന്റുചെയ്യുക, ഇതാണ് ജോഡി.
    3. അല്ലെങ്കിൽ സെറ്റിലേക്ക് arr [i] ചേർക്കുക.

വിശദീകരണം

ഞങ്ങൾ ഒരു പ്രശ്‌ന പ്രസ്താവന നൽകി, അതിൽ ഞങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ശ്രേണിയും ഒരു സംഖ്യ 'സം' എന്ന് പറയുന്നു. തന്നിരിക്കുന്ന “തുക” ന് തുല്യമായ ഒരു സംഗ്രഹം ഉള്ള രണ്ട് ഘടകങ്ങളിൽ ഏതെങ്കിലും ഒരു അറേയിൽ ഉണ്ടോ എന്ന് നിർണ്ണയിക്കുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല.

ഞങ്ങളുടെ പ്രധാന ആശയം ഹാഷ്‌സെറ്റ് ഉപയോഗിക്കുന്നതും ഒരു ജോഡി കണ്ടെത്തുന്നതുമാണ്. ഇതിനായി സഞ്ചരിക്കുമ്പോൾ സംഖ്യയുടെ വ്യത്യാസവും അറേയുടെ ഓരോ മൂല്യവും ഞങ്ങൾ സംഭരിക്കാൻ പോകുന്നു, കാരണം ഒരു ജോഡിക്ക് ആ രണ്ട് ഘടകങ്ങളാണുള്ളത്, തന്നിരിക്കുന്ന തുക മറ്റൊരു മൂലകം കണ്ടെത്തുന്നതിനുള്ള താക്കോലാണ്, അതിനാലാണ് ഞങ്ങൾ എല്ലാ അറേ ഘടകങ്ങളും സെറ്റിലേക്ക് സംഭരിക്കുന്നത് ജോഡികളിലെ ഘടകങ്ങളിലൊന്ന് നിലവിലുണ്ടോ ഇല്ലയോ എന്ന് പരിശോധിക്കുക.

ഇത് കണ്ടെത്താൻ, ഞങ്ങൾ ഒരു ഹാഷിംഗ് രീതി ഉപയോഗിക്കും.

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

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

  • i = 0, മൈസെറ്റ്, തുക = 16;

j = sum-arr [i];

അത് j = 16-1 = 15 ആണ്, തീർച്ചയായും 'j' ഒരു മാപ്പിൽ ഉണ്ടാകില്ല.

അതിനാൽ ഇത് മൈസെറ്റിലേക്ക് '1' ആയ arr [i] ചേർക്കുന്നു.

  • i = 1, മൈസെറ്റ് = {1}, തുക = 16;

j = sum-arr [i];

അത് j = 16-4 = 12 ആണ്, തീർച്ചയായും 'j' ഒരു മാപ്പിൽ ഇല്ല.

അതിനാൽ ഇത് മൈസെറ്റിലേക്ക് '4' ആയ arr [i] ചേർക്കുന്നു.

  • i = 2, മൈസെറ്റ് = {1, 4}, തുക = 16;

j = sum-arr [i];

അത് j = 16-45 = -29 ആണ്, തീർച്ചയായും 'j' ഒരു മാപ്പിൽ ഉണ്ടാകില്ല.

അതിനാൽ ഇത് മൈസെറ്റിലേക്ക് '45' ആയ arr [i] ചേർക്കുന്നു.

  • i = 3, മൈസെറ്റ് = {1, 4, 45}, തുക = 16;

j = sum-arr [i];

അത് j = 16-6 = 10, j ഒരു മാപ്പിൽ ഇല്ല.

അതിനാൽ ഇത് മൈസെറ്റിലേക്ക് '6' ആയ arr [i] ചേർക്കുന്നു.

  • i = 4, മൈസെറ്റ് = {1, 4, 45, 6}, തുക = 16;

j = sum-arr [i];

അത് j = 16-10 = 6, j മാപ്പിൽ ഉണ്ട്.

ഇവിടെയാണ് ജോഡിയുടെ മറ്റൊരു ഘടകം ഞങ്ങൾ കണ്ടെത്തുന്നത്. ഞങ്ങൾ ഇതിനകം 16, 10 തീയതികളിൽ പ്രവർത്തനം നടത്തി.

ഞങ്ങൾ അച്ചടിക്കുന്നു:

“തന്നിരിക്കുന്ന തുക 16 ആയി കണ്ടെത്തിയ ഘടകങ്ങൾ (10, 6);

അതിനർത്ഥം “സം” ന് തുല്യമായ ഒരു സംഖ്യയുള്ള രണ്ട് ഘടകങ്ങൾ അറേയിൽ ഉണ്ട്.

നടപ്പിലാക്കൽ

തന്നിരിക്കുന്ന തുകയ്‌ക്കൊപ്പം കൗണ്ട് ജോഡിക്കായുള്ള സി ++ പ്രോഗ്രാം

#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)

തന്നിരിക്കുന്ന തുകയ്‌ക്കൊപ്പം കൗണ്ട് ജോഡിക്കായുള്ള സങ്കീർണ്ണത വിശകലനം

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

O (n) മുഴുവൻ അറേയും ഒരു തവണ മാത്രം സഞ്ചരിക്കേണ്ടതിനാൽ.

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

O (n) അറേ ഘടകങ്ങൾ സംഭരിക്കാൻ ഒരു ഹാഷ് മാപ്പ് ഉപയോഗിച്ചതിനാൽ.

അവലംബം