Bir massivdə bütün cütləri (a, b) a% b = k olan şəkildə tapın

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Arcezium Citadel Directi Pulsuz yükləmə Yahoo
Geyim Sükut Modul hesabıBaxılıb 39

Problem bəyanat

Bir massivdə "a b) -nin bütün cütlərini tapın ki, a% b = k" sizə bir ədəd tam sıra və verilən bir tam dəyər verildiyini bildirir k. Problem ifadəsi cütlüyün bir sıra şəkildə x% y = k (verilmiş dəyər) olduğu kimi tapılmasını xahiş edir.

misal

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

Izahat

Bu 4 cüt% b = k doğru olduqda təsdiq edilmişdir.

Bir massivdə bütün cütləri (a, b) a% b = k olan şəkildə tapınPin

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

Izahat

Bu 3 cüt% b = k doğru olduqda təsdiq edilmişdir.

Alqoritm

  1. Bəyan edin a xəritə və arqumentlərindən birini a kimi seçin Boolean.
  2. Orijinalı keçin array və massivin bütün dəyərlərini əsl Boole dəyəri ilə xəritədə saxlayın.
  3. Hər hansı bir Boole dəyişənini söyləyin cüt yoxlayın yalan.
  4. Massivi 0-dan n-1-ə qədər keçin (n sıra uzunluğu).
    1. Verilən k dəyərinin bir xəritədə bir girişin olub olmadığını və k-nin cari sıra elementindən kiçik olduğunu yoxlayın. Doğrudursa, k dəyərini və o sıra elementini də yazdırın və bu Boole dəyərini true olaraq təyin edin.
    2. K-nin cari massiv elementindən az və ya bərabər olduğunu yoxlayın.
      1. Doğrudursa, bir vektor yaradın və arr [i] -k dəyərinin bütün bölücülərini tapın və vektorda saxlayın.
      2. O vektoru keçin və həmin vektor elementinin və massiv elementinin modul başa çatdıqda şərti təmin edən cütlüyünü yoxlayın.
        1. Vektor və cari sıra elementini çap edin və Boole dəyərini true olaraq təyin edin.
  5. Qayıtmaq cüt yoxlayın.

Izahat

Bir sıra ədədi və bir k dəyəri verilmişdir. Cütlüyü elə tapın ki, bir cüt (x, y) üzərində x% y = k kimi bir modul əməliyyatı yerinə yetirdiyimiz zaman bu cütü yazdırmalıyıq, bunu bütün tam sıra ilə etməliyik. X% y ədədi üzərində modul əməliyyatı apararkən k dəyəri verən bütün cütləri tapın. Bunun üçün vektor və xəritə adlı kolleksiyalardan birini və ya STL-dən istifadə edəcəyik.

Dizinin bütün elementlərini xəritəyə daxil edin və hamısını “əsl” Boole dəyəri ilə qeyd edin. Adlı bir Boolean dəyişənini başlatmalıyıq cüt yoxlayın yalan. Doğru cütü tapdıqda yeniləyəcəyik. onda indi dizini keçəcəyik. Verilən k dəyərinin xəritədə olub olmadığını yoxlayın. Həm də k cari sıra elementindən azdırsa. Sonra yalnız o cütü çap edirik. Çünki kiçik ədədi daha böyük rəqəmə böldükdə, qalanı kiçik rəqəm olaraq qoyacaqdır.

Yuxarıdakı şərt yalan olarsa, cari elementin k-dən böyük olub olmadığını yoxlayırıq. Doğrudursa, cari sıra elementinin və k-nin fərqini ötürdüyümüz bir vektor elan etməyimiz lazımdır ki, bu da cüt cütlərin mümkün olduğu dəyərləri qaytaracaqdır. Dəyərin hər birini seçəcəyik və vektordakı cari massiv elementinin modulla qaytarılmış dəyərinin k qalanını verdiyini və ya verməməsini yoxlayacağıq. Doğrudursa, cütü yazdırın və cüt dəyərini doğru olaraq qeyd edin, yəni ən azı bir cüt tapdıq. Eyni addımlarla əlavə dəyərlə davam edin və mümkün olan bütün nəticələri çap edin.

Kodu

Bir massivdə bütün cütləri (a, b) a% b = k olduğu qədər tapmaq üçün C ++ tətbiqetmə

#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)

Bir massivdə bütün cütləri (a, b)% b = k səviyyəsində tapmaq üçün Java kodu

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)

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n * sqrt (max)) hara “Max” massivdəki maksimum elementdir. Bu dəfə mürəkkəbliyə səbəb istifadə olundu

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır. Bu boşluq elementlərin xəritədə saxlanılması üçün tələb olunur.

Translate »