अ‍ॅरेमध्ये सर्व जोड्या (अ, बी) शोधा ज्यात% b = k


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

समस्या विधान

अ‍ॅरेमधील सर्व जोड्या (अ, बी) शोधा जसे की% b = k ”असे म्हणतात की आपल्याला पूर्णांकांची अ‍ॅरे आणि पूर्णांक मूल्य म्हणतात. k. अडचणी स्टेटमेंटमध्ये अ‍ॅरे मध्ये x% y = k (दिलेली व्हॅल्यू) अशा प्रकारे जोडी शोधण्यास सांगितले जाते.

उदाहरण

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

स्पष्टीकरण

% B = k सत्य असल्यास या 4 जोडांची पुष्टी केली गेली आहे.

अ‍ॅरेमध्ये सर्व जोड्या (अ, बी) शोधा ज्यात% b = k

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 आणि त्या अ‍ॅरे एलिमेंटची प्रिंट करून ती बुलियन व्हॅल्यू true वर सेट करा.
    2. के सध्याच्या अ‍ॅरे घटकापेक्षा कमी किंवा समान आहे का ते तपासा.
      1. खरे असल्यास एक वेक्टर तयार करा आणि अरर [i] -k व्हॅल्यूचे सर्व भाग शोधून त्यास वेक्टरमध्ये साठवा.
      2. त्या वेक्टरला मागे टाका आणि वेक्टर आणि अ‍ॅरे घटकांचा तो घटक जोडी आहे की नाही हे तपासा जे मोड्युलो झाल्यावर कंडिशन पूर्ण करते.
        1. वेक्टर आणि वर्तमान अ‍ॅरे घटक प्रिंट करा आणि बुलियन मूल्य सत्य वर सेट करा.
  5. परत जोडीचेक.

स्पष्टीकरण

पूर्णांकांची अ‍ॅरे आणि पूर्णांक मूल्य दिले. ही जोडी अशा प्रकारे शोधा की जेव्हा आपण जोडी (x, y) अशा x% y = k वर मॉड्यूलो ऑपरेशन करतो, तेव्हा आपल्याला ती जोडी प्रिंट करणे आवश्यक असते, हे पूर्ण पूर्णांक अ‍ॅरेसह करावे लागेल. जेव्हा आपण x% y क्रमांकावर मॉड्यूलो ऑपरेशन करतो तेव्हा त्या सर्व जोड्या शोधा जे के मूल्य देतात. त्यासाठी आम्ही संकलन किंवा एसटीएल नावाचा एक व्हॅक्टर आणि नकाशा वापरणार आहोत.

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

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

कोड

अ‍ॅरेमध्ये सर्व जोड्या (अ, बी) शोधण्यासाठी सी ++ मध्ये अंमलबजावणी जसे की% बी = के

#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)

अ‍ॅरेमध्ये सर्व जोड्या (अ, बी) शोधण्यासाठी जावा कोड जसे की% b = k

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)

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * वर्गमीटर (कमाल)) जेथे “कमाल” अ‍ॅरे मधील जास्तीत जास्त घटक आहे. यावेळी वापरल्यामुळे जटिलता प्राप्त झाली

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. नकाशामध्ये घटक साठवण्यासाठी ही जागा आवश्यक आहे.