מצא את כל הזוגות (a, b) במערך כך ש-% b = k


רמת קושי קשה
נשאל לעתים קרובות אמזון בעברית ארצסיום מצודה דירקטי חינם תשלום יאהו
מערך בליל אריתמטיקה מודולרית

הצהרת בעיה

הבעיה "מצא את כל הזוגות (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)

הסבר

4 הזוגות הללו אושרו כאשר% b = k נכון.

מצא את כל הזוגות (a, b) במערך כך ש-% b = k

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

הסבר

3 הזוגות הללו אושרו כאשר% b = k נכון.

אַלגוֹרִיתְם

  1. הכריז א מַפָּה ובחר אחד מטיעוניו כ- בוליאני.
  2. חצו את המקור מערך ולאחסן את כל הערכים של המערך עם ערך בוליאני אמיתי במפה.
  3. הגדר כל משתנה בוליאני לומר pairCheck לשקר.
  4. חצו את המערך בין 0 ל- n-1 (n הוא אורך המערך).
    1. בדוק אם לערך k הנתון יש ערך במפה וגם k קטן מאלמנט המערך הנוכחי. אם נכון, הדפס את הערך k וגם את אלמנט המערך הזה והגדר את הערך הבוליאני לאמיתי.
    2. בדוק אם k קטן או שווה לאלמנט המערך הנוכחי.
      1. אם נכון אז צור וקטור ומצא את כל המחלקים בערך arr [i] -k ושמור אותו בווקטור.
      2. חצו את הווקטור הזה ובדקו אם האלמנט הזה של הווקטור ואלמנט המערך הוא זוג שעונה על התנאי כאשר נעשה מודולו.
        1. הדפיסו את וקטור ורכיב המערך הנוכחי והגדרו את הערך הבוליאני לאמיתי.
  5. לחזור pairCheck.

הסבר

ניתן מערך של מספרים שלמים וערך שלם k. מצא את הצמד באופן שכאשר אנו מבצעים פעולת מודולו על זוג (x, y) כך ש-%% = k, אז עלינו להדפיס את הזוג הזה, עלינו לעשות זאת עם מערך שלם שלם. מצא את כל אותם זוגות שנותנים את הערך k כאשר אנו מבצעים פעולת מודולו במספר x% y. לשם כך אנו נשתמש באחד האוספים או STL הנקרא וקטור ומפה.

הכניסו את כל רכיבי המערך למפה וסמנו את כולם בערך בוליאני "אמיתי". עלינו לאתחל משתנה בוליאני שנקרא pairCheck לשקר. אנו הולכים לעדכן אותו כשנמצא את הזוג הנכון. ואז נעבור עכשיו על המערך. ובדוק אם ערך k הנתון קיים במפה או לא. גם אם k קטן מאלמנט המערך הנוכחי. ואז אנחנו רק מדפיסים את הזוג הזה. מכיוון שכאשר נחלק מספר קטן במספר גדול יותר הוא ישאיר את השאר כמספר קטן.

אם התנאי הנ"ל הופך לשגוי, נבדוק אם האלמנט הנוכחי גדול מ- k. אם נכון, עלינו להכריז על וקטור שבו אנו מעבירים את ההפרש של אלמנט המערך הנוכחי ו- k, שיחזיר את הווקטור בו מוחזרים הצמדים הערכים האפשריים. אנו נבחר כל אחד מהערכים ונבדוק אם אלמנט המערך הנוכחי מודולו שהוחזר בווקטור נותן את שארית k או לא. אם זה נכון אז הדפיס את הצמד וסמן את ערך pairCheck כנכון, כלומר מצאנו לפחות זוג אחד. המשך לערך נוסף באותם השלבים והדפס את כל התוצאות האפשריות.

קופונים

יישום ב- 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)

קוד Java למציאת כל הזוגות (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 (מקסימום)) איפה "מקסימום" הוא האלמנט המרבי במערך. מורכבות הזמן הזו הושגה כי השתמשנו

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. מקום זה נדרש לאחסון האלמנטים במפה.