गिव सम के साथ जोड़ी को गिनें


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट वीरांगना FactSet वृद्धि
ऐरे hashing मठ छंटाई

समस्या में "दी गई राशि के साथ गणना जोड़ी" हमने एक पूर्णांक दिया है सरणी[] और एक अन्य संख्या 'योग' कहती है, आपको यह निर्धारित करना होगा कि किसी दिए गए सरणी में दोनों तत्वों में से कोई एक राशि "योग" के बराबर है।

उदाहरण

इनपुट:

arr [] = {1,3,4,6,7} और योग = 9।

आउटपुट:

“तत्व दिए गए के साथ मिला sum ”जैसा कि '3’ और' 6 ’हैं जिसमें योग बराबर है '9' को।

इनपुट:

arr [] = {11,3,5,7,10} और योग = 20।

आउटपुट:

"तत्व दिए गए योग के साथ नहीं मिला है" क्योंकि ऐसी कोई संख्या नहीं है जो '8' के बराबर है।

कलन विधि

  1. डिक्लेयर ए सेट.
  2. जबकि 0 से 'i' सरणी की लंबाई से कम है।
    1. J-to sum-arr [i] सेट करें।
    2. जांचें कि क्या सेट में 'जे' है, अगर सही है तो जे प्रिंट करें और गिरफ्तार करें [i], यह जोड़ी होगी।
    3. सेट में गिरफ्तार [i] को जोड़ दें।

व्याख्या

हमने एक समस्या बयान दिया है, जिसमें हमें पूर्णांक सरणी और एक संख्या 'योग' के साथ दी गई है। हमारा कार्य यह निर्धारित करना है कि किसी सरणी में दो तत्वों में से कोई एक है, जो किसी दिए गए "योग" के बराबर है।

हमारा मुख्य विचार हैसेट का उपयोग करना और एक जोड़ी खोजना है। जिसके लिए हम ट्रावर्स करते समय योग और सरणी के प्रत्येक मान के अंतर को संग्रहीत करने जा रहे हैं, क्योंकि एक जोड़ी में दो तत्व हैं और एक दिए गए योग में एक और तत्व खोजने की कुंजी है, यही कारण है कि हम सभी सरणी तत्वों को सेट में संग्रहीत करते हैं। और इस पर गौर करें कि जोड़ी में कोई एक तत्व मौजूद है या नहीं।

इसका पता लगाने के लिए, हम एक हैशिंग विधि का उपयोग करेंगे।

एक उदाहरण लेते हैं:

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

  • i = 0, myset, योग = 16;

j = sum-arr [i];

वह j = 16-1 = 15 है और निश्चित रूप से 'j' एक मानचित्र में मौजूद नहीं होगा।

इसलिए यह गिरफ्तारी [i] को जोड़ देता है जो '1' है।

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

j = sum-arr [i];

वह j = 16-4 = 12 है और निश्चित रूप से 'j' एक मानचित्र में मौजूद नहीं है।

इसलिए यह गिरफ्तारी [i] को जोड़ देता है जो '4' है।

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

j = sum-arr [i];

वह j = 16-45 = -29 है और निश्चित रूप से 'j' एक मानचित्र में नहीं होगा।

इसलिए यह गिरफ्तारी [i] को जोड़ देता है जो '45' है।

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

j = sum-arr [i];

यह j = 16-6 = 10 है और j एक मानचित्र में मौजूद नहीं है।

इसलिए यह गिरफ्तारी [i] को जोड़ देता है जो '6' है।

  • i = 4, myset = {1, 4, 45, 6}, sum = 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)

काउंट जोड़ी के लिए जटिलता विश्लेषण गिव सम के साथ

समय जटिलता

पर) के रूप में पूरे सरणी केवल एक बार पता लगाया जा करने की आवश्यकता है।

अंतरिक्ष जटिलता

पर) सरणी तत्वों को संग्रहीत करने के लिए हैश मैप के रूप में उपयोग किया गया है।

संदर्भ