ሁሉንም ጥንዶች (ሀ ፣ ለ) በአንድ ድርድር ውስጥ ያግኙ% b = k


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን አርሴሲየም ግልብጥብጥ Directi ፍሪጅ ቻርጅ ያሁ
ሰልፍ ሃሽ ሞዱል ሂሳብ

የችግሩ መግለጫ

ችግሩ “ሁሉንም ጥንድ (ሀ ፣ ለ) በአንድ ድርድር ውስጥ ያግኙ% 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 እውነት ሲሆኑ ተረጋግጠዋል ፡፡

ሁሉንም ጥንዶች (ሀ ፣ ለ) በአንድ ድርድር ውስጥ ያግኙ% b = k

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

ማስረጃ

እነዚህ 3 ጥንዶች% b = k እውነት ሲሆኑ ተረጋግጠዋል ፡፡

አልጎሪዝም

  1. ያውጅ ሀ ካርታ እና ከክርክሩ ውስጥ አንዱን ይምረጡ ሀ ቡሊያን.
  2. ዋናውን አቋርጠው ደርድር የድርድሩ ሁሉንም እሴቶች በእውነተኛ የቦሊያን እሴት በካርታው ላይ ያከማቹ።
  3. ለመናገር ማንኛውንም የቦሊያን ተለዋዋጭ ያዘጋጁ ጥንድ ቼክ ወደ ሐሰት.
  4. ድርድርውን ከ 0 ወደ n-1 ያቋርጡ (n የድርድሩ ርዝመት ነው)።
    1. የተሰጠው k እሴት በካርታ ውስጥ መግቢያ እንዳለው ያረጋግጡ እና እንዲሁም k አሁን ካለው የድርድር አካል ያነሰ ነው። እውነት ከሆነ ፣ ከዚያ እሴቱን k እና እንዲሁም ያንን የድርድር አካል ያትሙና ያንን የቦሊያን እሴት ወደ እውነት ያዋቅሩ።
    2. ኪው አሁን ካለው የድርድር አካል ያነሰ ወይም እኩል መሆኑን ያረጋግጡ።
      1. እውነት ከሆነ ታዲያ ቬክተር ይፍጠሩ እና የአር [i] -k እሴት ሁሉንም ከፋዮች ያግኙ እና ወደ ቬክተሩ ውስጥ ያከማቹ።
      2. ያንን ቬክተር ያቋርጡ እና ያ የቬክተር እና የድርድር አካል ሞጁሎው ሲጠናቀቅ ሁኔታውን የሚያሟላ ጥንድ ከሆኑ ያረጋግጡ።
        1. ቬክተሩን እና የወቅቱን ድርድር አባል ያትሙና የቦሊያንን እሴት ወደ እውነት ያዋቅሩ።
  5. ተመለስ ጥንድ ቼክ.

ማስረጃ

ብዛት ያላቸው የቁጥር ቁጥሮች እና ኢንቲጀር እሴት k. ጥንድ ጥንድ ፈልገው ያግኙ በአንድ ጥንድ (x, y) ላይ እንደዚህ ባለ x% y = k ላይ የሞዱሎ አሠራርን ስናከናውን ያንን ጥንድ ማተም ያስፈልገናል ፣ ይህንን በጠቅላላው ኢንቲጀር ድርድር ማድረግ አለብን ፡፡ በቁጥር x% y ላይ የሞዱሎ አሠራርን ስናከናውን ዋጋ k የሚሰጡትን እነዚህን ሁሉ ጥንዶች ፈልግ ፡፡ ለዚህም ቬክተር እና ካርታ ከሚሉት ስብስቦች ውስጥ አንዱን ወይም STL ን እንጠቀማለን ፡፡

ሁሉንም የድርጅት አባሎች በካርታው ውስጥ ያስገቡ እና ሁሉንም በ “እውነተኛ” የቦሊያን እሴት ምልክት ያድርጉባቸው። የተጠራውን የቦሊያን ተለዋዋጭ ማስጀመር ያስፈልገናል ጥንድ ቼክ ወደ ሐሰት. ትክክለኛውን ጥንድ ስናገኝ እናዘምነዋለን ፡፡ ከዚያ አሁን ድርድርን እናቋርጣለን ፡፡ እና የተሰጠው k እሴት በካርታ ውስጥ ካለ ወይም አለመሆኑን ያረጋግጡ። እንዲሁም k አሁን ካለው የድርድር አካል ያነሰ ከሆነ። ከዚያ ያንን ጥንድ ብቻ እናተም ፡፡ ምክንያቱም አነስተኛ ቁጥርን በትልቁ ቁጥር ስናካፍል ቀሪውን እንደ ትንሽ ቁጥር ይተዋል።

ከላይ ያለው ሁኔታ ሐሰት ከሆነ ፣ አሁን ያለው ንጥረ ነገር ከኬ የበለጠ መሆኑን እንፈትሻለን። እውነት ከሆነ እንግዲያውስ ጥንድ ሊሆኑ የሚችሉ እሴቶች የሚመለሱበትን ቬክተር የሚመልሰውን የአሁኑን የድርድር እና የ k ልዩነትን የምናልፍበትን ቬክተር ማወጅ ያስፈልገናል ፡፡ እያንዳንዱን እሴት እንመርጣለን እና በቬክተሩ ውስጥ የአሁኑ የድርድር ሞዱሎ የተመለሰ እሴት ቀሪውን ኪ ወይም እንደማይሰጥ እንፈትሻለን ፡፡ እውነት ከሆነ ታዲያ ጥንድውን ያትሙ እና ጥንድ ቼክ እሴቱን እንደ እውነት ምልክት ያድርጉበት ፣ ይህም ማለት ቢያንስ አንድ ጥንድ አግኝተናል ማለት ነው ፡፡ በተመሳሳዩ እርምጃዎች ተጨማሪ እሴት ይቀጥሉ እና ሁሉንም ሊሆኑ የሚችሉ ውጤቶችን ያትሙ።

ኮድ

ሁሉንም ጥንድ (ሀ ፣ ለ) በአንድ ድርድር ውስጥ ለማግኘት በ ‹ሲ› ውስጥ ተግባራዊነት እንደዚህ% 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)

ሁሉንም ጥንዶች (ሀ ፣ ለ) በአንድ ድርድር ውስጥ ለማግኘት የጃቫ ኮድ እንደዚህ% 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)

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n * sqrt (max)) የት “ከፍተኛ” በድርድሩ ውስጥ ከፍተኛው ንጥረ ነገር ነው። እኛ ስለምንጠቀምበት ይህ ጊዜ ውስብስብነት ተገኝቷል

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። በካርታው ውስጥ ያሉትን ንጥረ ነገሮች ለማከማቸት ይህ ቦታ ያስፈልጋል።