Намерете всички двойки (a, b) в масив, така че a% b = k  


Ниво на трудност Трудно
Често задавани в Амазонка Арцезиум Цитадела Директи FreeCharge Yahoo
Array Хашиш Модулна аритметика

Декларация за проблема  

Проблемът „Намерете всички двойки (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 = kщифт

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

Обяснение

Тези 3 двойки са потвърдени, когато a% b = k е вярно.

алгоритъм  

  1. Декларирайте а карта и изберете един от аргументите му като a Булева.
  2. Прекоси оригинала масив и съхранява всички стойности на масива с истинска булева стойност в картата.
  3. Задайте всяка булева променлива да казва чифтпроверете да фалшива.
  4. Преминете масива от 0 до n-1 (n е дължината на масива).
    1. Проверете дали дадената k стойност има запис в карта и също така k е по-малка от текущия елемент на масива. Ако е вярно, тогава отпечатайте стойността k, а също и този елемент на масива и задайте тази булева стойност на true.
    2. Проверете дали k е по-малко или равно на текущия елемент на масива.
      1. Ако е вярно, създайте вектор и намерете всички делители на стойността arr [i] -k и го запазете във вектора.
      2. Прекосете този вектор и проверете дали този елемент от вектора и елемента от масив са двойка, което отговаря на условието, когато е изпълнено по модул.
        1. Отпечатайте елемента вектор и текущ масив и задайте логическата стойност на true.
  5. връщане чифтпроверете.
Вижте също
Най-малкият елемент, повторен точно K пъти

Обяснение  

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

Поставете всички елементи на масива в картата и ги маркирайте с „истинска“ булева стойност. Трябва да инициализираме булева променлива, наречена чифтпроверете до фалшив. Ще го актуализираме, когато намерим правилната двойка. тогава ще прекосим масива сега. И проверете дали дадената k стойност присъства в карта или не. Също така, ако k е по-малко от текущия елемент на масив. След това просто отпечатваме тази двойка. Защото когато разделим малко число на по-голямо, остатъкът ще остане като малко число.

Ако горното условие стане невярно, тогава проверяваме дали текущият елемент е по-голям от k. Ако е вярно, тогава трябва да декларираме вектор, където предаваме разликата на текущия елемент на масива и 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 (макс.)) където „Макс“ е максималният елемент в масива. Този път сложността беше постигната, защото използвахме

Вижте също
Преобразуване на масив в намалена форма

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Това пространство е необходимо за съхраняване на елементите в картата.