ఇచ్చిన మొత్తంతో జత కౌంట్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అకోలైట్ అమెజాన్ ఫాక్ట్‌సెట్ హైక్
అర్రే హ్యాషింగ్ మఠం సార్టింగ్

సమస్యలో “ఇచ్చిన మొత్తంతో జత లెక్కించండి” మేము పూర్ణాంకం ఇచ్చాము అమరిక[] మరియు మరొక సంఖ్య 'మొత్తం' అని చెప్తుంది, ఇచ్చిన శ్రేణిలోని రెండు మూలకాలలో ఏదైనా "మొత్తం" కు సమానమైన మొత్తం ఉందో లేదో మీరు నిర్ణయించుకోవాలి.

ఉదాహరణ

ఇన్పుట్:

arr [] = {1,3,4,6,7} మరియు మొత్తం = 9.

అవుట్పుట్:

"ఇచ్చిన మూలకాలు కనుగొనబడ్డాయి మొత్తం ”సమానమైన '3' మరియు '6' ఉన్నందున '9' కు.

ఇన్పుట్:

arr [] = {11,3,5,7,10} మరియు మొత్తం = 20.

అవుట్పుట్:

'ఇచ్చిన మొత్తంతో మూలకాలు కనుగొనబడలేదు "ఎందుకంటే' 8 'కు సమానమైన మొత్తం సంఖ్య లేదు.

అల్గారిథం

  1. ప్రకటించండి a సెట్.
  2. 0 నుండి 'i' శ్రేణి యొక్క పొడవు కంటే తక్కువగా ఉంటుంది.
    1. J ను sum-arr [i] కు సెట్ చేయండి.
    2. సెట్‌లో 'j' ఉందో లేదో తనిఖీ చేయండి, నిజమైతే j మరియు arr [i] ను ప్రింట్ చేయండి, ఇది జత అవుతుంది.
    3. లేకపోతే సెట్లో అర్ర్ [i] ను జోడించండి.

వివరణ

మేము ఒక సమస్య స్టేట్మెంట్ ఇచ్చాము, దీనిలో మనకు పూర్ణాంక శ్రేణితో ఇవ్వబడుతుంది మరియు ఒక సంఖ్య 'మొత్తం' అని చెప్పబడుతుంది. ఇచ్చిన “మొత్తానికి” సమానమైన సమ్మషన్ ఉన్న రెండు మూలకాలలో శ్రేణికి ఏదైనా ఉందా అని నిర్ణయించడం మా పని.

మా ప్రధాన ఆలోచన హాష్‌సెట్‌ను ఉపయోగించడం మరియు ఒక జతను కనుగొనడం. దీని కోసం మేము ప్రయాణించేటప్పుడు మొత్తం మరియు శ్రేణి యొక్క ప్రతి విలువను నిల్వ చేయబోతున్నాము, ఎందుకంటే ఒక జతకి ఆ రెండు మూలకాలు ఉన్నాయి మరియు ఇచ్చిన మొత్తం మరొక మూలకాన్ని కనుగొనటానికి కీలకం, అందుకే మేము అన్ని శ్రేణి మూలకాలను సెట్‌లోకి నిల్వ చేస్తాము మరియు జతలోని మూలకాలలో ఒకటి ఉందా లేదా అని పరిశీలించండి.

దీన్ని తెలుసుకోవడానికి, మేము హాషింగ్ పద్ధతిని ఉపయోగిస్తాము.

ఒక ఉదాహరణ తీసుకుందాం:

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

  • i = 0, మైసెట్, మొత్తం = 16;

j = sum-arr [i];

అది j = 16-1 = 15 మరియు ఖచ్చితంగా 'j' మ్యాప్‌లో ఉండదు.

కనుక ఇది మైసెట్‌లోకి '1' అయిన అర్ర్ [i] ను జోడిస్తుంది.

  • i = 1, మైసెట్ = {1}, మొత్తం = 16;

j = sum-arr [i];

అది j = 16-4 = 12 మరియు ఖచ్చితంగా 'j' మ్యాప్‌లో ఉండదు.

కనుక ఇది మైసెట్‌లోకి '4' అయిన అర్ర్ [i] ను జోడిస్తుంది.

  • i = 2, మైసెట్ = {1, 4}, మొత్తం = 16;

j = sum-arr [i];

అది j = 16-45 = -29 మరియు ఖచ్చితంగా 'j' మ్యాప్‌లో ఉండదు.

కనుక ఇది మైసెట్‌లోకి '45' అయిన అర్ర్ [i] ను జోడిస్తుంది.

  • i = 3, మైసెట్ = {1, 4, 45}, మొత్తం = 16;

j = sum-arr [i];

అంటే j = 16-6 = 10 మరియు j ఒక మ్యాప్‌లో లేదు.

కనుక ఇది మైసెట్‌లోకి '6' అయిన అర్ర్ [i] ను జోడిస్తుంది.

  • i = 4, మైసెట్ = {1, 4, 45, 6}, మొత్తం = 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)

ఇచ్చిన మొత్తంతో కౌంట్ జత కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) మొత్తం శ్రేణి ఒక్కసారి మాత్రమే ప్రయాణించాల్సిన అవసరం ఉంది.

అంతరిక్ష సంక్లిష్టత

పై) శ్రేణి మూలకాలను నిల్వ చేయడానికి హాష్ మ్యాప్ ఉపయోగించబడింది.

సూచన