Գտեք զանգվածի բոլոր զույգերը (a, b) այնպես, որ a% b = k  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Արսիսիում Միջնաբերդ Դիրեկտի Անվճար լիցքավորում Անտաշ անասուն նողկալի արարած
Դասավորություն Խանգարել Մոդուլային թվաբանություն

Խնդիրի հայտարարություն  

«Գտեք բոլոր զույգերը (a, b) զանգվածում այնպես, որ a% b = k» խնդիրը նշում է, որ ձեզ տրվում է ամբողջ թվերի զանգված և կոչվում է ամբողջ արժեք: k, Խնդրի հայտարարությունը խնդրում է զույգը պարզել այնպես, որ զանգվածում x% y = k (տրված արժեք):

Օրինակ  

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

բացատրություն

Այս 4 զույգերը հաստատվել են, երբ% b = k ճշմարիտ է:

Գտեք զանգվածի բոլոր զույգերը (a, b) այնպես, որ a% b = kPin

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

բացատրություն

Այս 3 զույգերը հաստատվել են, երբ% b = k ճշմարիտ է:

Ալգորիթմ  

  1. Հայտարարել ա Քարտեզը և ընտրեք դրա փաստարկներից մեկը որպես a Boolean.
  2. Տարօրինակեք բնօրինակը դասավորություն և պահեք քարտեզում իրական բուլյան արժեք ունեցող զանգվածի բոլոր արժեքները:
  3. Սահմանեք ասելու ցանկացած բուլյան փոփոխական զույգ Ստուգեք կեղծ:
  4. Անցեք զանգվածը 0-ից n-1 (n- ի զանգվածի երկարությունը):
    1. Ստուգեք, արդյոք տրված k արժեքը մուտք ունի քարտեզում, և նաև k փոքր է, քան ընթացիկ զանգվածի տարրը: Եթե ​​ճիշտ է, ապա տպիր k արժեքը, ինչպես նաև զանգվածի այդ տարրը և այդ բուլյան արժեքը դարձրու ճշմարիտ:
    2. Ստուգեք, արդյոք k- ն պակաս է կամ հավասար է ընթացիկ զանգվածի տարրին:
      1. Եթե ​​ճիշտ է, ապա ստեղծիր վեկտոր և գտիր arr [i] -k արժեքի բոլոր բաժանարարներին և պահիր վեկտորի մեջ:
      2. Անցեք այդ վեկտորը և ստուգեք, արդյոք վեկտորի և զանգվածի տարրի այդ տարրը զույգ է, որը բավարարում է մոդուլի կատարման պայմանը:
        1. Տպեք վեկտորի և ընթացիկ զանգվածի տարրը և բուլյան արժեքը դարձրեք true:
  5. Վերադառնալ զույգ Ստուգեք.
Տես նաեւ,
Ամենափոքր տարրը կրկնվեց հենց K Times- ը

բացատրություն  

Հաշվի առնելով ամբողջ թվերի զանգվածը և ամբողջ արժեքը k. Գտեք զույգը այնպես, որ երբ մենք կատարում ենք զույգի (x, y) մոդուլի գործողություն այնպես, որ x% y = k, ապա մենք պետք է տպենք այդ զույգը, դա պետք է անենք ամբողջ ամբողջ զանգվածով: Գտեք բոլոր այն զույգերը, որոնք տալիս են k արժեքը, երբ մենք կատարում ենք x% y թվով մոդուլի գործողություն: Դրա համար մենք պատրաստվում ենք օգտագործել հավաքածուներից մեկը կամ STL, որը կոչվում է վեկտոր և քարտեզ:

Rayանգվածի բոլոր տարրերը դրեք քարտեզի վրա և բոլորն էլ նշեք «իրական» բուլյան արժեքով: Մենք պետք է նախանշենք բուլյան փոփոխական, որը կոչվում է զույգ Ստուգեք կեղծ Մենք պատրաստվում ենք այն թարմացնել, երբ գտնենք ճիշտ զույգը: ապա մենք հիմա անցնելու ենք զանգվածը: Եվ ստուգեք ՝ տրված k արժեքը քարտեզում առկա է, թե ոչ: Նաև, եթե k- ն պակաս է ընթացիկ զանգվածի տարրից: Հետո մենք պարզապես տպում ենք այդ զույգը: Քանի որ երբ փոքր թիվը բաժանենք ավելի մեծի, այն կթողնի մնացորդը որպես փոքր թիվ:

Եթե ​​վերը նշված պայմանը կեղծ է դառնում, ապա մենք ստուգում ենք ՝ արդյո՞ք ընթացիկ տարրը մեծ է k- ից: Եթե ​​ճիշտ է, ապա մենք պետք է հայտարարենք վեկտոր, որտեղ մենք անցնում ենք ընթացիկ զանգվածի տարրի և k- ի տարբերությունը, որը կվերադարձնի այն վեկտորը, որի դեպքում վերադարձվում են զույգերի հնարավոր արժեքները: Մենք պատրաստվում ենք ընտրել արժեքներից յուրաքանչյուրը և ստուգել `վեկտորում առկա զանգվածի տարրերի մոդուլի վերադարձված արժեքը տալիս է մնացորդ k- ն, թե ոչ: Եթե ​​դա ճիշտ է, ապա տպիր զույգը և նշիր զույգի ստուգման արժեքը որպես ճշմարիտ, ինչը նշանակում է, որ մենք գտել ենք առնվազն մեկ զույգ: Հետագա արժեքով շարունակեք նույն քայլերով և տպեք բոլոր հնարավոր արդյունքները:

Տես նաեւ,
Հաջորդականության երկրորդ կրկնվող բառը

Կոդ  

Իրականացում C ++ - ում `զանգվածում բոլոր զույգերը (a, b) գտնելու համար, որպեսզի a% 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)

Java կոդ ՝ զանգվածում բոլոր զույգերը (a, b) գտնելու համար այնպես, որ a% 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)

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n * sqrt (առավելագույն)) որտեղ «Մաքս» զանգվածում առավելագույն տարրն է: Այս անգամ բարդությունը ձեռք բերվեց այն պատճառով, որ մենք օգտագործեցինք

Տես նաեւ,
Convertանգվածը վերափոխեք կրճատված ձևի

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Այս տարածքը պահանջվում է քարտեզում տարրերը պահելու համար: