एरेमा सबै जोडीहरू (a, b) फेला पार्नुहोस् जस्तो कि% b = k


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन आर्सेसियम Citadel Directi फ्रीचार्ज याहू
एरे हैश मोड्युलर अंकगणित

समस्या वक्तव्य

समस्या "एरेमा सबै जोडीहरू (a, b) फेला पार्नुहोस् जस्तो कि% b = k" बताउँछ कि तपाईंलाई पूर्णांकको एरे र एक पूर्णांक मान भनिन्छ। k। समस्या कथनले जोडीलाई यसरी पत्ता लगाउँदछ कि एर्रेमा x% y = k (दिएको मान)।

उदाहरणका

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

स्पष्टीकरण

यी pairs जोडीहरू निश्चित गरियो जब% b = k सही हुन्छ।

एरेमा सबै जोडीहरू (a, b) फेला पार्नुहोस् जस्तो कि% b = k

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

स्पष्टीकरण

यी pairs जोडीहरू निश्चित गरियो जब% b = k सही हुन्छ।

अल्गोरिदम

  1. घोषणा गर्नुहोस् नक्सा र यसको एक आर्गुमेन्टलाई a को रूपमा चयन गर्नुहोस् बूलियन.
  2. मूल पार गर्नुहोस् array र एर्रेको सबै मानहरू नक्शामा सही बुलियन मानको साथ भण्डारण गर्नुहोस्।
  3. भन्नको लागि कुनै बुलियन भ्यारीएबल सेट गर्नुहोस् जोडी चेक गलत गर्न।
  4. 0 बाट n-1 (n एर्रे को लम्बाई हो) बाट एर्रे पार गर्नुहोस्।
    1. यदि दिइएको k मानको नक्शामा प्रविष्ट छ र जाँच गर्नुहोस् पनि हालको एरे एलिमेन्ट भन्दा सानो छ कि छैन जाँच गर्नुहोस्। यदि सहि छ भने, तब मान k प्रिन्ट गर्नुहोस् र त्यो एरे एलिमेन्ट र सेट गर्नुहोस कि बुलियन मानलाई सहि।
    2. जाँच गर्नुहोस् कि यदि के वर्तमान एर्रे एलिमेन्ट भन्दा कम वा बराबर छ।
      1. यदि सहि छ भने एक भेक्टर बनाउनुहोस् र एररको ii [i] -k मानका डिभिडरहरू फेला पार्नुहोस् र भेक्टरमा भण्डार गर्नुहोस्।
      2. त्यो भेक्टरलाई ट्र्यावर्स गर्नुहोस् र जाँच गर्नुहोस् कि भेक्टर र एर्रे एलिमेन्टको त्यो तत्व जोडी हो जसले मोडुलो गरेपछि सर्त पूरा गर्दछ।
        1. भेक्टर र वर्तमान एर्रे एलिमेन्ट प्रिन्ट गर्नुहोस् र बुलियन मानलाई सहीमा सेट गर्नुहोस्।
  5. फिर्ती जोडी चेक.

स्पष्टीकरण

पूर्णा of्कको एरे र पूर्णांक मान k जोडीलाई यस्तो तरिकाले फेला पार्नुहोस् कि जब हामी जोडी (x, y) मा मोडुलो अपरेसन गर्छौं त्यस्ता x% y = k, तब हामीले त्यो जोडी प्रिन्ट गर्न आवश्यक पर्दछ, हामीले पूर्ण इन्टिजर एरेसँग यो गर्नु पर्छ। ती सबै जोडीहरू फेला पार्नुहोस् जसले मान k दिन्छ जब हामी संख्या x% y मा मोडुलो अपरेसन गर्छौं। यसको लागि, हामी सlections्कलनहरू वा STL भनिने भेक्टर र नक्सा मध्ये एक प्रयोग गर्नेछौं।

नक्शामा एर्रे एलिमेन्टहरू सबै राख्नुहोस् र ती सबैलाई "साँचो" बुलियन मानको साथ मार्क गर्नुहोस्। हामीले बुलियन भ्यारीएबल भनिने सुरूवात गर्नु पर्छ जोडी चेक गलत गर्न। हामी यसलाई अपडेट गर्न गइरहेका छौं जब हामी सहि जोडी पाउँछौं। त्यसोभए हामी अब एर्रेलाई पार गर्न जाँदैछौं। र जाँच गर्नुहोस् यदि दिईएको k मान मानचित्रमा छ वा छैन। यदि k हालको एरे एलिमेन्ट भन्दा कम छ भने। त्यसो भए हामी केवल त्यो जोडी प्रिन्ट गर्दछौं। किनभने जब हामी सानो संख्यालाई ठूलो संख्यामा विभाजन गर्छौं भने यसले शेष संख्यालाई सानो संख्याको रूपमा छोड्छ।

यदि माथिको सर्त गलत भए, हामी जाँच गर्छौं कि यदि हालको एलिमेन्ट k भन्दा ठूलो छ भने। यदि सहि छ भने, त्यसो भए हामीले भेक्टर घोषणा गर्नु पर्छ जहाँ हामी हालको एर्रे एलिमेन्ट र k को फरक पार गर्छौं, जसले भेक्टरलाई फर्काउँछ जसमा जोडी सम्भावित मानहरू फर्काउँछ। हामी प्रत्येक मान छनौट गर्न जानेछौं र जाँच गर्नुहोस् कि यदि वर्तमान एर्रे एलिमेन्ट मोडुलोले भेक्टरमा फिर्ता मान दिएको छ वा बाँकी के। यदि यो सत्य हो भने जोडी प्रिन्ट गर्नुहोस् र जोडीचेक मानलाई सहीको रूपमा चिन्ह लगाउनुहोस्, जसको अर्थ हामीले कमसेकम एउटा जोडी भेट्यौं। उही चरणहरूको साथ थप मानको साथ अगाडि बढ्नुहोस् र सबै सम्भावित परिणामहरू प्रिन्ट गर्नुहोस्।

कोड

C ++ मा कार्यान्वयन एरेमा सबै जोडीहरू (a, b) खोज्नको लागि जस्तो कि% b = k

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

जाभा कोड एरेमा सबै जोडीहरू (a, b) खोज्नका लागि कि% 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 * sqrt (अधिकतम)) जहाँ "अधिकतम" एर्रेमा अधिकतम तत्व हो। यो समय जटिलता हासिल गरियो किनकि हामीले प्रयोग गर्‍यौं

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। यो स्थान को नक्शा मा तत्वहरु को भण्डारण को लागी आवश्यक छ।