অ্যারেতে সমস্ত জোড় (ক, খ) সন্ধান করুন যেমন একটি% বি = কে


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

সমস্যা বিবৃতি

সমস্যাটি "অ্যারেতে সমস্ত জোড় (ক, খ) সন্ধান করুন যেমন একটি% বি = কে" সূচিত করে যে আপনাকে পূর্ণসংখ্যার অ্যারে এবং একটি পূর্ণসংখ্যা মান বলা হয় k। সমস্যা বিবৃতিটি জোড়টিকে এমনভাবে সন্ধান করতে বলে যে অ্যারেতে x% y = কে (প্রদত্ত মান)।

উদাহরণ

arr[] = {3, 4, 7, 5, 6 }
k = 3
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

ব্যাখ্যা

% B = k সত্য হলে এই 4 টি জোড়া নিশ্চিত হয়ে গেছে।

অ্যারেতে সমস্ত জোড় (ক, খ) সন্ধান করুন যেমন একটি% বি = কে

arr[]={2, 3, 5, 1},
k = 2
(2, 3) (2, 5) (5, 3)

ব্যাখ্যা

% B = k সত্য হলে এই 3 টি জোড়া নিশ্চিত হয়ে গেছে।

অ্যালগরিদম

  1. ঘোষণা করুন ক মানচিত্র এবং এর হিসাবে একটি আর্গুমেন্ট নির্বাচন করুন বুলিয়ান.
  2. আসলটি অতিক্রম করুন বিন্যাস এবং অ্যারের সমস্ত মান মানচিত্রে সত্য বুলিয়ান মান সহ সঞ্চয় করুন।
  3. বলতে গেলে যে কোনও বুলিয়ান ভেরিয়েবল সেট করুন পেয়ারচেক মিথ্যা।
  4. 0 থেকে n-1 (n অ্যারের দৈর্ঘ্য) থেকে অ্যারেটি অতিক্রম করুন।
    1. প্রদত্ত কে মানটির কোনও মানচিত্রে প্রবেশ রয়েছে এবং তাও বর্তমান অ্যারে উপাদানের চেয়ে ছোট কিনা তা পরীক্ষা করে দেখুন। যদি সত্য হয় তবে মান k এবং সেই অ্যারে উপাদানটি মুদ্রণ করুন এবং সেই বুলিয়ান মানটিকে সত্য হিসাবে সেট করুন।
    2. বর্তমানের অ্যারে উপাদানটির তুলনায় কে কম বা সমান কিনা তা পরীক্ষা করুন।
      1. যদি সত্য হয় তবে একটি ভেক্টর তৈরি করুন এবং আরার [i] -k মানটির সমস্ত বিভাজনগুলি সন্ধান করুন এবং এটি ভেক্টরে সংরক্ষণ করুন।
      2. সেই ভেক্টরটিকে অতিক্রম করুন এবং ভেক্টর এবং অ্যারের উপাদানটির উপাদানটি জোড়া রয়েছে কিনা তা যাচাই করুন যখন মডুলো সম্পন্ন হওয়ার পরে শর্তটি সন্তুষ্ট হয়।
        1. ভেক্টর এবং বর্তমান অ্যারে উপাদানটি মুদ্রণ করুন এবং বুলিয়ান মানটিকে সত্য হিসাবে সেট করুন।
  5. প্রত্যাবর্তন পেয়ারচেক.

ব্যাখ্যা

একটি পূর্ণসংখ্যার অ্যারের এবং একটি পূর্ণসংখ্যার মান k দেওয়া হয়েছে। জুটিটি এমনভাবে সন্ধান করুন যাতে যখন আমরা কোনও জোড় (x, y) এর মতো x% y = k এর উপর একটি মডুলো অপারেশন করি, তখন আমাদের সেই জুটিটি মুদ্রণ করা দরকার, আমাদের এটি পুরো পূর্ণসংখ্য অ্যারে দিয়ে করতে হবে। সমস্ত সংখ্যক জোড়গুলি সন্ধান করুন যা মান x দেয় যখন আমরা একটি সংখ্যার x% y এ একটি মডুলো অপারেশন করি। এর জন্য, আমরা সংগ্রহ বা STL নামক ভেক্টর এবং মানচিত্রের একটি ব্যবহার করতে যাচ্ছি।

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

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

কোড

একটি অ্যারেতে সমস্ত জোড় (ক, খ) খুঁজে পেতে সি ++ এ বাস্তবায়ন যেমন একটি% বি = কে

#include <unordered_map>
#include<vector>
#include<iostream>
#include<math.h>

using namespace std;

vector<int> findPossibleDiv(int n)
{
    vector<int> vecDiv;

    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            if (n / i == i)
                vecDiv.push_back(i);
            else
            {
                vecDiv.push_back(i);
                vecDiv.push_back(n / i);
            }
        }
    }
    return vecDiv;
}
bool pairModulousK(int arr[], int n, int k)
{
    unordered_map<int, bool> MAP;
    for (int i = 0; i < n; i++)
        MAP[arr[i]] = true;

    bool pairCheck = false;
    for (int i = 0; i < n; i++)
    {
        if (MAP[k] && k < arr[i])
        {
            cout << "(" << k << ", " << arr[i] << ") ";
            pairCheck = true;
        }
        if (arr[i] >= k)
        {
            vector<int> vec = findPossibleDiv(arr[i] - k);

            for (int j = 0; j < vec.size(); j++)
            {
                if (arr[i] % vec[j] == k && arr[i] != vec[j] && MAP[vec[j]])
                {
                    cout << "(" << arr[i] << ", "<< vec[j] << ") ";
                    pairCheck = true;
                }
            }
            vec.clear();
        }
    }
    return pairCheck;
}
int main()
{
    int arr[] = { 3, 4, 7, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    if (pairModulousK(arr, n, k) == false)
        cout << "No such pair exists";
    return 0;
}
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

জাভা কোডটি অ্যারেতে সমস্ত জোড় (ক, খ) খুঁজে পেতে যেমন একটি% বি = কে

import java.util.HashMap;
import java.util.Vector;

class PairModuloK
{
    public static Vector<Integer> findPossibleDiv(int n)
    {
        Vector<Integer> vecDiv = new Vector<>();

        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
                if (n / i == i)
                    vecDiv.add(i);
                else
                {
                    vecDiv.add(i);
                    vecDiv.add(n / i);
                }
            }
        }
        return vecDiv;
    }
    public static boolean pairModulousK(int arr[], int n, int k)
    {
        HashMap<Integer, Boolean> MAP = new HashMap<>();
        for (int i = 0; i < n; i++)
            MAP.put(arr[i], true);

        boolean pairCheck = false;
        for (int i = 0; i < n; i++)
        {
            if (MAP.get(k) && k < arr[i])
            {
                System.out.print("(" + k + ", " + arr[i] + ") ");
                pairCheck = true;
            }
            if (arr[i] >= k)
            {
                Vector<Integer> vec = findPossibleDiv(arr[i] - k);

                for (int j = 0; j < vec.size(); j++)
                {
                    if (arr[i] % vec.get(j) == k && arr[i] != vec.get(j) && MAP.get(vec.get(j)))
                    {
                        System.out.print("(" + arr[i] + ", "
                                         + vec.get(j) + ") ");
                        pairCheck = true;
                    }
                }
                vec.clear();
            }
        }

        return pairCheck;
    }
    public static void main(String args[])
    {
        int arr[] = {3, 4, 7, 6, 5};
        int k = 3;

        if (pairModulousK(arr, arr.length, k) == false)
            System.out.println("No such pair exists");
    }
}
(3, 4) (3, 7) (7, 4) (3, 6) (3, 5)

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন * বর্গ (সর্বোচ্চ)) কোথায় "সর্বোচ্চ" অ্যারের সর্বাধিক উপাদান। এই সময় জটিলতা অর্জন করা হয়েছিল কারণ আমরা ব্যবহার করি

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। মানচিত্রের উপাদানগুলি সংরক্ষণ করার জন্য এই স্থানটি প্রয়োজনীয়।