% 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. చెప్పడానికి ఏదైనా బూలియన్ వేరియబుల్ సెట్ చేయండి pairCheck తప్పుడు.
  4. శ్రేణిని 0 నుండి n-1 వరకు ప్రయాణించండి (n అనేది శ్రేణి యొక్క పొడవు).
    1. ఇచ్చిన k విలువకు మ్యాప్‌లో ఎంట్రీ ఉందా మరియు ప్రస్తుత శ్రేణి మూలకం కంటే k చిన్నదా అని తనిఖీ చేయండి. నిజమైతే, k విలువను మరియు ఆ శ్రేణి మూలకాన్ని కూడా ప్రింట్ చేసి, ఆ బూలియన్ విలువను ఒప్పుకు సెట్ చేయండి.
    2. K ప్రస్తుత శ్రేణి మూలకం కంటే తక్కువ లేదా సమానంగా ఉందో లేదో తనిఖీ చేయండి.
      1. నిజమైతే వెక్టర్‌ను సృష్టించి, అర్ర్ [i] -k విలువ యొక్క అన్ని విభజనలను కనుగొని వెక్టర్‌లో నిల్వ చేయండి.
      2. ఆ వెక్టర్‌లో ప్రయాణించి, వెక్టర్ మరియు అర్రే ఎలిమెంట్ యొక్క మూలకం జతగా ఉందో లేదో తనిఖీ చేయండి, ఇది మాడ్యులో పూర్తయినప్పుడు పరిస్థితిని సంతృప్తిపరుస్తుంది.
        1. వెక్టర్ మరియు ప్రస్తుత శ్రేణి మూలకాన్ని ముద్రించండి మరియు బూలియన్ విలువను ఒప్పుకు సెట్ చేయండి.
  5. రిటర్న్ pairCheck.

వివరణ

పూర్ణాంకాల శ్రేణి మరియు పూర్ణాంక విలువ k ఇవ్వబడింది. X% y = k వంటి జత (x, y) పై మాడ్యులో ఆపరేషన్ చేసినప్పుడు, ఆ జంటను ప్రింట్ చేయాలి, మేము దీన్ని పూర్తి పూర్ణాంక శ్రేణితో చేయాలి. మేము x% y సంఖ్యపై మాడ్యులో ఆపరేషన్ చేసినప్పుడు k విలువను ఇచ్చే అన్ని జతలను కనుగొనండి. దీని కోసం, మేము వెక్టర్ మరియు మ్యాప్ అని పిలువబడే సేకరణలలో ఒకటి లేదా STL ను ఉపయోగించబోతున్నాము.

అన్ని శ్రేణి మూలకాలను మ్యాప్‌లో ఉంచండి మరియు అవన్నీ “నిజమైన” బూలియన్ విలువతో గుర్తించండి. మేము బూలియన్ వేరియబుల్ అని పిలవాలి 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” శ్రేణిలోని మూలకాల సంఖ్య. మ్యాప్‌లోని మూలకాలను నిల్వ చేయడానికి ఈ స్థలం అవసరం.