প্রদত্ত সমের সাথে জুটি গণনা করুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি মর্দানী স্ত্রীলোক ফ্যাক্সেট আরোহণ
বিন্যাস হ্যাশ ম্যাথ শ্রেণীবিভাজন

সমস্যাটিতে "প্রদত্ত অঙ্কের সাথে গণনা জোড়া" আমরা একটি পূর্ণসংখ্যা দিয়েছি বিন্যাস[] এবং অন্য একটি সংখ্যা 'সমষ্টি' বলে, আপনাকে নির্ধারণ করতে হবে প্রদত্ত অ্যারেতে দুটি উপাদানের মধ্যে কোনওটির যোগফল "যোগফল" এর সমান কিনা।

উদাহরণ

ইনপুট:

অ্যারে [] = {1,3,4,6,7} এবং যোগফল = 9।

আউটপুট:

“প্রদত্তের সাথে উপাদানগুলি পাওয়া গেল সমষ্টি "যেমন '3' এবং '6' রয়েছে যার সমান পরিমাণ রয়েছে '9' থেকে।

ইনপুট:

অ্যারে [] = {11,3,5,7,10} এবং যোগফল = 20।

আউটপুট:

"প্রদত্ত অঙ্কের সাথে উপাদানগুলি পাওয়া যায় নি" কারণ কোনও সংখ্যা নেই যার যোগফল '8' এর সমান হয়।

অ্যালগরিদম

  1. ঘোষণা করুন ক সেট.
  2. 0 থেকে 'i' অ্যারের দৈর্ঘ্যের তুলনায় কম।
    1. যোগফলকে যোগফলে সেট করুন [i]।
    2. সেটে 'জ' রয়েছে কিনা তা পরীক্ষা করুন, যদি সত্য হয় তবে জে এবং আর্ট প্রিন্ট করুন [i], এটি জুটি হবে।
    3. অন্যথায় সেটে আরআর [i] যুক্ত করুন।

ব্যাখ্যা

আমরা একটি সমস্যার বিবৃতি দিয়েছি, যাতে আমাদের পূর্ণসংখ্য অ্যারে এবং একটি সংখ্যা 'সমষ্টি' বলে দেওয়া হয়। আমাদের কাজটি নির্ধারণ করা হয় যে অ্যারের দুটি প্রদত্ত "যোগফল" এর সমান সংখ্যার দুটি উপাদানের কোনও রয়েছে কিনা তা নির্ধারণ করা।

আমাদের মূল ধারণাটি হ্যাশসেট ব্যবহার করা এবং একটি জুড়ি খুঁজে পাওয়া। যার জন্য আমরা ট্র্যাভারিংয়ের সময় যোগফল এবং অ্যারের প্রতিটি মানের পার্থক্য সংরক্ষণ করতে যাচ্ছি কারণ একটি জুটিতে সেই দুটি উপাদান রয়েছে এবং প্রদত্ত যোগটি অন্য একটি উপাদান খুঁজে বের করার মূল চাবিকাঠি, এজন্য আমরা অ্যারে উপাদানগুলির সমস্তটিকে সেটে সংরক্ষণ করি এবং জোড়ের উপাদানগুলির মধ্যে একটি উপস্থিত হয় বা না থাকলে এটি সন্ধান করুন।

এটি খুঁজে পেতে, আমরা একটি হ্যাশিং পদ্ধতি ব্যবহার করব।

চল একটি উদাহরণ দিই:

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

  • i = 0, মাইসেট, যোগ = 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)

প্রদত্ত অঙ্কের সাথে গণনা জুটির জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) যেহেতু পুরো অ্যারেটি একবারে ট্র্যাভার করা দরকার।

স্পেস জটিলতা ity

উপর) হ্যাশ ম্যাপ হিসাবে অ্যারে উপাদানগুলি সংরক্ষণ করার জন্য ব্যবহৃত হয়েছে।

উল্লেখ