दिलेल्या योगासह जोडणी जोडा


अडचण पातळी सोपे
वारंवार विचारले एकत्रित ऍमेझॉन फॅक्टसेट वाढ
अरे हॅशिंग गणित वर्गीकरण

समस्येमध्ये "दिलेल्या योगासह मोजणी जोडा" आम्ही एक पूर्णांक दिला आहे अॅरे[] आणि दुसरी संख्या 'बेरीज' म्हणते, दिलेल्या अ‍ॅरेमधील दोन घटकांपैकी कोणत्याही एकाची बेरीज "बेरीज" समान आहे की नाही हे आपण निर्धारित केले पाहिजे.

उदाहरण

इनपुट:

अरे [] = {1,3,4,6,7} आणि बेरीज = 9.

आउटपुट:

“दिलेल्या घटकांसह आढळले बेरीज ”जसे की 3 आणि 6 आहेत ज्यात बेरीज समान आहेत '9' पर्यंत

इनपुट:

अरे [] = {11,3,5,7,10} आणि बेरीज = 20.

आउटपुट:

'दिलेल्या बेरीजसह घटक सापडले नाहीत' कारण '8' च्या बरोबरीची कोणतीही संख्या नाही.

अल्गोरिदम

  1. घोषित ए संच.
  2. तर 0 ते 'i' अ‍ॅरेच्या लांबीपेक्षा कमी आहे.
    1. बेरीज करण्यासाठी आर सेट करा [i].
    2. सेटमध्ये 'j' समाविष्ट आहे का ते तपासा, खरे असल्यास j आणि एर प्रिंट करा [i], ही जोडी असेल.
    3. अन्यथा सेटमध्ये अरर [i] जोडा.

स्पष्टीकरण

आम्ही प्रॉब्लेम स्टेटमेंट दिले आहे, ज्यामध्ये आपल्याला इंटिजेस अ‍ॅरे दिले आहेत आणि एक संख्या 'बेरीज' देते. आमचे कार्य अ‍ॅरेमध्ये दोन घटकांपैकी कोणतेही एक दिलेली “बेरीज” च्या बरोबरीची बेरीज आहे की नाही हे निर्धारित करणे आहे.

हॅशसेटचा वापर करणे आणि एक जोडी शोधणे ही आमची मुख्य कल्पना आहे. ज्यासाठी आम्ही ट्रॅव्हर्सिंग करताना बेरीजचा फरक आणि अ‍ॅरेचे प्रत्येक मूल्य संचयित करणार आहोत, कारण जोड्यामध्ये त्या दोन घटक असतात आणि दिलेली बेरीज आणखी एक घटक शोधण्याची गुरुकिल्ली असते, म्हणूनच आम्ही अ‍ॅरेचे सर्व घटक सेटमध्ये संग्रहित करतो. आणि जोडीतील घटकांपैकी एखादा एकतर विद्यमान आहे किंवा नसल्यास त्याकडे लक्ष द्या.

हे शोधण्यासाठी आम्ही हॅशिंग पद्धत वापरू.

चला एक उदाहरण घेऊ:

अरे [] = {1, 4, 45, 6, 10, 8};

  • i = 0, myset, बेरीज = 16;

j = बेरीज-एर [i];

ते j = 16-1 = 15 आहे आणि निश्चितपणे 'j' नकाशामध्ये उपस्थित राहणार नाहीत.

तर हे मायसेटमध्ये अरर [i] जो '1' आहे.

  • i = 1, मायसेट = {1}, बेरीज = 16;

j = बेरीज-एर [i];

ते j = 16-4 = 12 आहे आणि निश्चितच 'j' नकाशामध्ये उपस्थित नाही.

तर हे मायसेटमध्ये अरर [i] जो '4' आहे.

  • i = 2, मायसेट = {1, 4}, बेरीज = 16;

j = बेरीज-एर [i];

ते j = 16-45 = -29 आहे आणि निश्चितपणे 'j' नकाशामध्ये नसतील.

तर हे मायसेटमध्ये अरर [i] जो '45' आहे.

  • i = 3, मायसेट = {1, 4, 45}, बेरीज = 16;

j = बेरीज-एर [i];

ते j = 16-6 = 10 आहे आणि j नकाशामध्ये उपस्थित नाहीत.

तर हे मायसेटमध्ये अरर [i] जो '6' आहे.

  • i = 4, मायसेट = {1, 4, 45, 6}, बेरीज = 16;

j = बेरीज-एर [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) अ‍ॅरे घटक संचयित करण्यासाठी हॅश नकाशाचा वापर केला गेला आहे.

संदर्भ