એરેમાં બધી જોડીઓ (એ, બી) શોધો જેમ કે% b = k  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે એમેઝોન આર્સેસીયમ સિટાડેલ ડાયરેક્ટિ ફ્રીચાર્જ યાહૂ
અરે હેશ મોડ્યુલર અંકગણિત

સમસ્યા નિવેદન  

સમસ્યા "એરેમાં બધા જોડીઓ (એ, બી) શોધો જેમ કે% b = k" જણાવે છે કે તમને પૂર્ણાંકોની એરે આપવામાં આવે છે અને પૂર્ણાંક મૂલ્ય કહેવાય છે. k. સમસ્યાનું નિવેદન એ જોડીને એવી રીતે શોધવા માટે કહે છે કે એરેમાં x% y = k (આપેલ મૂલ્ય).

ઉદાહરણ  

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

સમજૂતી

જ્યારે% b = k સાચું હોય ત્યારે આ 4 જોડીઓની પુષ્ટિ કરવામાં આવી છે.

એરેમાં બધી જોડીઓ (એ, બી) શોધો જેમ કે% b = kપિન

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

સમજૂતી

જ્યારે% b = k સાચું હોય ત્યારે આ 3 જોડીઓની પુષ્ટિ કરવામાં આવી છે.

અલ્ગોરિધમ  

  1. ઘોષણા કરો એ નકશો અને તેની દલીલોમાંથી એક પસંદ કરો બુલિયન.
  2. મૂળને વટાવી દો એરે અને એરેના બધા મૂલ્યોને નકશામાં સાચા બુલિયન મૂલ્ય સાથે સંગ્રહિત કરો.
  3. કહેવા માટે કોઈપણ બુલિયન ચલ સેટ કરો જોડી તપાસો ખોટા.
  4. 0 થી n-1 (n એરેની લંબાઈ છે) થી એરેને વટાવી દો.
    1. તપાસો કે આપેલ કે ના મૂલ્યમાં નકશામાં એન્ટ્રી છે કે કેમ અને વર્તમાન એરે એલિમેન્ટ કરતા પણ નાનું છે. જો સાચું હોય, તો પછી વેલ્યુ k અને એરે એલિમેન્ટ પણ છાપો અને તે બુલિયન વેલ્યુને ટ્રુ પર સુયોજિત કરો.
    2. તપાસો કે કે વર્તમાન એરે એલિમેન્ટથી ઓછું છે કે નહીં.
      1. જો સાચું હોય તો વેક્ટર બનાવો અને એઆરઆર [i] -k મૂલ્યના બધા વિભાજકો શોધો અને તેને વેક્ટરમાં સ્ટોર કરો.
      2. તે વેક્ટરને ઓળખો અને તપાસો કે વેક્ટર અને એરે એલિમેન્ટનો તે તત્વ જોડી છે જે મોડ્યુલો કરવામાં આવે ત્યારે શરતને સંતોષે છે.
        1. વેક્ટર અને વર્તમાન એરે એલિમેન્ટને છાપો અને બુલિયન વેલ્યુને ટ્રુ પર સેટ કરો.
  5. રીટર્ન જોડી તપાસો.
આ પણ જુઓ
સૌથી નાનું તત્ત્વ પુનરાવર્તિત બરાબર કે ટાઇમ્સ

સમજૂતી  

પૂર્ણાંકોની એરે અને પૂર્ણાંક મૂલ્ય કે. જોડીને એવી રીતે શોધો કે જ્યારે આપણે જોડી (x, y) જેમ કે x% y = k પર મોડ્યુલો ઓપરેશન કરીએ, તો પછી આપણે તે જોડી છાપવાની જરૂર છે, આપણે આને સંપૂર્ણ પૂર્ણાંક એરે સાથે કરવું પડશે. તે બધા જોડીઓ શોધો કે જ્યારે આપણે x% y નંબર પર મોડ્યુલો ઓપરેશન કરીએ ત્યારે કે જે k ને વેલ્યુ આપે છે. આ માટે, અમે સંગ્રહ અથવા STL નામના વેક્ટર અને નકશામાંથી એકનો ઉપયોગ કરવા જઈશું.

બધા એરે તત્વોને નકશામાં મૂકો અને તે બધાને "સાચા" બુલિયન મૂલ્યથી ચિહ્નિત કરો. આપણે બુલીયન વેરિયેબલ કહેવાતા પ્રારંભ કરવાની જરૂર છે જોડી તપાસો ખોટા. જ્યારે આપણે સાચી જોડી શોધીશું ત્યારે અમે તેને અપડેટ કરવા જઈશું. તો આપણે હવે એરેને પસાર કરીશું. અને તપાસો કે આપેલ કે મૂલ્ય નકશામાં હાજર છે કે નહીં. જો કે વર્તમાન એરે એલિમેન્ટ કરતા ઓછું હોય. પછી અમે ફક્ત તે જોડી છાપીશું. કારણ કે જ્યારે આપણે નાની સંખ્યાને મોટી સંખ્યામાં વહેંચીએ છીએ ત્યારે તે બાકીનીને એક નાની સંખ્યા તરીકે છોડી દેશે.

જો ઉપરની સ્થિતિ ખોટી થઈ જાય, તો આપણે તપાસ કરીશું કે વર્તમાન તત્વ 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 * ચોરસ (મહત્તમ)) જ્યાં “મહત્તમ” એરેમાં મહત્તમ તત્વ છે. આ સમય જટિલતા પ્રાપ્ત થઈ હતી કારણ કે અમે ઉપયોગમાં લીધા છે

આ પણ જુઓ
એરેને ઘટાડેલા ફોર્મમાં ફેરવો

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. નકશામાં તત્વો સંગ્રહવા માટે આ જગ્યા આવશ્યક છે.