Знайдіть усі пари (a, b) у масиві такі, що a% b = k  


Рівень складності Жорсткий
Часто запитують у Амазонка Арцезіум Цитадель Directi FreeCharge Yahoo
масив Мішанина Модульна арифметика

Постановка проблеми  

Задача “Знайти всі пари (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 пари були підтверджені, коли a% b = k відповідає дійсності.

Знайдіть усі пари (a, b) у масиві такі, що a% b = kPin

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

Пояснення

Ці 3 пари були підтверджені, коли a% b = k відповідає дійсності.

Алгоритм  

  1. Заявіть a карта і виберіть один із аргументів як a Boolean.
  2. Перемістіть оригінал масив і збережіть усі значення масиву з істинним булевим значенням на карті.
  3. Встановіть будь-яку логічну змінну, щоб вимовити параПеревірка до помилкового.
  4. Перемістіть масив від 0 до n-1 (n - довжина масиву).
    1. Перевірте, чи вказане значення k має запис на карті, а також k менше, ніж поточний елемент масиву. Якщо true, тоді надрукуйте значення k, а також цей елемент масиву та встановіть для цього логічного значення значення true.
    2. Перевірте, чи k менше або дорівнює поточному елементу масиву.
      1. Якщо true, тоді створіть вектор і знайдіть усі дільники значення arr [i] -k та збережіть його у векторі.
      2. Пройдіть по цьому вектору та перевірте, чи є цей елемент вектора та елемента масиву парою, що задовольняє умові, коли виконано модуль.
        1. Надрукуйте вектор і поточний елемент масиву та встановіть для логічного значення значення true.
  5. Повертати параПеревірка.
Дивись також
Найменший елемент, повторений рівно K разів

Пояснення  

Дано масив цілих чисел і ціле значення k. Знайдіть пару таким чином, що коли ми виконуємо модульну операцію над парою (x, y) таку, що x% y = k, тоді нам потрібно надрукувати цю пару, ми повинні робити це з цілим цілим масивом. Знайдіть усі ті пари, які дають значення k, коли ми виконуємо модульну операцію над числом x% y. Для цього ми будемо використовувати одну з колекцій або STL, що називається вектор і карта.

Помістіть усі елементи масиву на карту і позначте їх усіх істинним булевим значенням. Нам потрібно ініціалізувати булеву змінну з назвою параПеревірка до помилкового. Ми будемо оновлювати його, коли знайдемо правильну пару. тоді ми збираємось пройти масив зараз. І перевірте, чи вказане значення k присутнє на карті чи ні. Також якщо k менше, ніж поточний елемент масиву. Тоді ми просто друкуємо цю пару. Тому що, коли ми ділимо невелике число на більше число, це залишає решту як маленьке число.

Якщо вищевказана умова стає хибною, ми перевіряємо, чи поточний елемент не перевищує k. Якщо true, тоді нам потрібно оголосити вектор, де ми передаємо різницю поточного елементу масиву і k, який поверне вектор, в якому повертаються пари можливих значень. Ми збираємося вибрати кожне зі значень і перевірити, чи поточний елемент масиву, що повертається за модулем, у векторі дає залишок k чи ні. Якщо це істина, то надрукуйте пару і позначте значення pairCheck як true, що означає, що ми знайшли принаймні одну пару. Продовжуйте подальше значення з тими ж кроками та друкуйте всі можливі результати.

Дивись також
Друге найбільш часто повторюване слово в послідовності

код  

Реалізація в 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)

Аналіз складності  

Складність часу

O (n * sqrt (макс.)) де “Макс.” є максимальним елементом масиву. Цього часу складність була досягнута завдяки тому, що ми використовували

Дивись також
Перетворити масив у зменшену форму

Складність простору

О (п) де "N" - кількість елементів у масиві. Цей простір необхідний для зберігання елементів на карті.