% B = k போன்ற ஒரு வரிசையில் அனைத்து ஜோடிகளையும் (a, b) கண்டுபிடிக்கவும்  


சிரமம் நிலை கடின
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆர்சீசியம் சிட்டாடல் டைரக்டி ஃப்ரீசார்ஜ் யாகூ
அணி ஹாஷ் மட்டு எண்கணிதம்

சிக்கல் அறிக்கை  

“அனைத்து ஜோடிகளையும் (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)

விளக்கம்

% B = k உண்மையாக இருக்கும்போது இந்த 4 ஜோடிகள் உறுதிப்படுத்தப்பட்டுள்ளன.

% B = k போன்ற ஒரு வரிசையில் அனைத்து ஜோடிகளையும் (a, b) கண்டுபிடிக்கவும்

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

விளக்கம்

% B = k உண்மையாக இருக்கும்போது இந்த 3 ஜோடிகள் உறுதிப்படுத்தப்பட்டுள்ளன.

அல்காரிதம்  

  1. ஒரு அறிவிக்கவும் வரைபடம் அதன் வாதங்களில் ஒன்றை a எனத் தேர்ந்தெடுக்கவும் பூலியன்.
  2. அசலைக் கடந்து செல்லுங்கள் வரிசை உண்மையான பூலியன் மதிப்புடன் வரிசையின் அனைத்து மதிப்புகளையும் வரைபடத்தில் சேமிக்கவும்.
  3. சொல்ல எந்த பூலியன் மாறியையும் அமைக்கவும் ஜோடி சரிபார்க்கவும் பொய்.
  4. வரிசையை 0 முதல் n-1 வரை பயணிக்கவும் (n என்பது வரிசையின் நீளம்).
    1. கொடுக்கப்பட்ட k மதிப்பு ஒரு வரைபடத்தில் உள்ளீடு உள்ளதா என்றும், தற்போதைய வரிசை உறுப்பை விட k சிறியதா என்றும் சரிபார்க்கவும். உண்மை என்றால், k மதிப்பு மற்றும் அந்த வரிசை உறுப்பு ஆகியவற்றை அச்சிட்டு அந்த பூலியன் மதிப்பை உண்மை என அமைக்கவும்.
    2. K தற்போதைய வரிசை உறுப்புக்கு குறைவாகவோ அல்லது சமமாகவோ இருக்கிறதா என்று சோதிக்கவும்.
      1. உண்மை என்றால் ஒரு திசையனை உருவாக்கி, அர் [i] -k மதிப்பின் அனைத்து வகுப்பிகளையும் கண்டுபிடித்து அதை திசையனில் சேமிக்கவும்.
      2. அந்த திசையனைக் கடந்து, திசையன் மற்றும் வரிசை உறுப்புகளின் உறுப்பு ஜோடியாக இருக்கிறதா என்று சோதிக்கவும், இது மட்டு செய்யப்படும்போது நிலையை பூர்த்தி செய்கிறது.
        1. திசையன் மற்றும் தற்போதைய வரிசை உறுப்பை அச்சிட்டு பூலியன் மதிப்பை உண்மை என அமைக்கவும்.
  5. திரும்ப ஜோடி சரிபார்க்கவும்.
மேலும் காண்க
மிகச்சிறிய உறுப்பு சரியாக கே டைம்ஸ் மீண்டும் மீண்டும் செய்யப்பட்டது

விளக்கம்  

முழு எண்களின் வரிசை மற்றும் ஒரு முழு மதிப்பு k கொடுக்கப்பட்டுள்ளது. X% y = k போன்ற ஒரு ஜோடி (x, y) இல் ஒரு மட்டு செயல்பாட்டைச் செய்யும்போது, ​​அந்த ஜோடியை அச்சிட வேண்டும், இதை முழு முழு வரிசை வரிசையுடன் செய்ய வேண்டும். X% y எண்ணில் ஒரு மட்டு செயல்பாட்டைச் செய்யும்போது k மதிப்பைக் கொடுக்கும் அனைத்து ஜோடிகளையும் கண்டறியவும். இதற்காக, திசையன் மற்றும் வரைபடம் எனப்படும் தொகுப்புகளில் ஒன்றை அல்லது எஸ்.டி.எல்.

அனைத்து வரிசை கூறுகளையும் வரைபடத்தில் வைத்து அவை அனைத்தையும் “உண்மையான” பூலியன் மதிப்புடன் குறிக்கவும். நாம் ஒரு பூலியன் மாறியை துவக்க வேண்டும் ஜோடி சரிபார்க்கவும் பொய். சரியான ஜோடியைக் கண்டுபிடிக்கும்போது அதைப் புதுப்பிக்கப் போகிறோம். இப்போது நாம் வரிசையை கடந்து செல்லப் போகிறோம். கொடுக்கப்பட்ட k மதிப்பு ஒரு வரைபடத்தில் இருக்கிறதா இல்லையா என்பதைச் சரிபார்க்கவும். தற்போதைய வரிசை உறுப்பை விட k குறைவாக இருந்தால். பின்னர் அந்த ஜோடியை அச்சிடுகிறோம். ஏனென்றால், நாம் சிறிய எண்ணிக்கையை பெரிய எண்ணால் வகுக்கும்போது, ​​மீதமுள்ளதை ஒரு சிறிய எண்ணாக விட்டுவிடுவோம்.

மேலே உள்ள நிபந்தனை தவறானதாக இருந்தால், தற்போதைய உறுப்பு k ஐ விட அதிகமாக இருக்கிறதா என்று சரிபார்க்கிறோம். உண்மை என்றால், தற்போதைய வரிசை உறுப்பு மற்றும் k இன் வேறுபாட்டை நாம் கடந்து செல்லும் ஒரு திசையனை அறிவிக்க வேண்டும், இது ஜோடிகளின் சாத்தியமான மதிப்புகள் திரும்பும் திசையனை வழங்கும். நாம் ஒவ்வொரு மதிப்பையும் தேர்ந்தெடுத்து, திசையனில் தற்போதைய வரிசை உறுப்பு மட்டு திரும்பிய மதிப்பு மீதமுள்ள k ஐ அளிக்கிறதா இல்லையா என்பதை சரிபார்க்கப் போகிறோம். அது உண்மையாக இருந்தால், ஜோடியை அச்சிட்டு, ஜோடிசெக் மதிப்பை உண்மை எனக் குறிக்கவும், அதாவது குறைந்தபட்சம் ஒரு ஜோடியையாவது கண்டுபிடித்தோம். அதே படிகளுடன் மேலும் மதிப்புடன் தொடரவும் மற்றும் சாத்தியமான அனைத்து முடிவுகளையும் அச்சிடவும்.

மேலும் காண்க
ஒரு வரிசையில் இரண்டாவது மிக மீண்டும் மீண்டும் சொல்

குறியீடு  

ஒரு% b = k போன்ற ஒரு வரிசையில் அனைத்து ஜோடிகளையும் (a, b) கண்டுபிடிக்க C ++ இல் செயல்படுத்தல்

#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 போன்ற ஒரு வரிசையில் அனைத்து ஜோடிகளையும் (a, b) கண்டுபிடிக்க ஜாவா குறியீடு

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) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. வரைபடத்தில் உள்ள கூறுகளை சேமிக்க இந்த இடம் தேவை.