% B = k වැනි අරාව තුළ සියලුම යුගල (a, b) සොයා ගන්න


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් ආකේසියම් සිටඩෙල් ඩිරෙක්ටි FreeCharge යාහූ
අරා හැෂ් මොඩියුලර් අංක ගණිතය

ගැටළු ප්රකාශය

“% B = k” වැනි අරාවකින් “සියලු යුගල (a, b) සොයා ගන්න” යන්නෙන් ඔබට පූර්ණ සංඛ්‍යා පෙළක් සහ පූර්ණ සංඛ්‍යාවක් ලබා දී ඇති බව සඳහන් වේ. 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. කීමට ඕනෑම බූලියන් විචල්‍යයක් සකසන්න pairCheck අසත්‍යයට.
  4. අරාව 0 සිට n-1 දක්වා ගමන් කරන්න (n යනු අරාවේ දිග).
    1. ලබා දී ඇති k අගයට සිතියමක ඇතුළත් කිරීමක් තිබේදැයි පරීක්ෂා කරන්න. සත්‍ය නම්, k අගය සහ එම අරාව මූලද්‍රව්‍යය මුද්‍රණය කර එම බූලියන් අගය සත්‍ය ලෙස සකසන්න.
    2. K වත්මන් අරාව මූලද්‍රව්‍යයට වඩා අඩු හෝ සමාන දැයි පරීක්ෂා කරන්න.
      1. සත්‍ය නම් දෛශිකයක් සාදා අර [i] -k අගයෙහි සියලු බෙදීම් සොයාගෙන එය දෛශිකයේ ගබඩා කරන්න.
      2. එම දෛශිකය හරහා ගමන් කර දෛශිකයේ සහ අරාවෙහි මූලද්‍රව්‍යයේ යුගලය මොඩියුලය සිදු කළ විට තත්වය තෘප්තිමත් කරන යුගලයක් දැයි පරීක්ෂා කරන්න.
        1. දෛශිකය සහ වත්මන් අරාව මූලද්‍රව්‍යය මුද්‍රණය කර බූලියන් අගය සත්‍ය ලෙස සකසන්න.
  5. ආපසු pairCheck.

පැහැදිලි කිරීම

නිඛිල සංඛ්‍යාවක් සහ පූර්ණ සංඛ්‍යාවක් k ලබා දී ඇත. X% y = k වැනි යුගලයක් (x, y) මත අපි මොඩියුලෝ මෙහෙයුමක් සිදු කරන විට, එම යුගලය මුද්‍රණය කළ යුතු වන පරිදි යුගලය සොයා ගන්න, අපි මෙය සම්පූර්ණ සංඛ්‍යා අරා සමඟ කළ යුතුය. අපි x% y අංකයකින් මොඩියුලෝ මෙහෙයුමක් සිදු කරන විට k අගය ලබා දෙන සියලුම යුගල සොයා ගන්න. මේ සඳහා අපි දෛශික සහ සිතියම නමින් එක් එකතුවක් හෝ එස්ටීඑල් භාවිතා කරන්නෙමු.

සියලුම අරාව මූලද්‍රව්‍ය සිතියමට දමා ඒවා සියල්ලම “සත්‍ය” බූලියන් අගයකින් සලකුණු කරන්න. අපි බූලියන් විචල්‍යයක් ආරම්භ කළ යුතුයි pairCheck අසත්‍යයට. නිවැරදි යුගලය සොයාගත් විට අපි එය යාවත්කාලීන කිරීමට යන්නෙමු. එහෙනම් අපි දැන් අරාව හරහා යන්නෙමු. ලබා දී ඇති 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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. සිතියමේ ඇති මූලද්රව්ය ගබඩා කිරීම සඳහා මෙම අවකාශය අවශ්ය වේ.