የእነሱ ምርቶች በድርድር ውስጥ የሚገኙትን ጥንዶች ይቆጥሩ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የተከማቸ አማዞን ብላክ ሮክ የሞንፎርግ ቤተ ሙከራዎች ኦላ ካብስ Snapchat ጎሜ
ሰልፍ ሃሽ

በቁጥር ጥንዶች ውስጥ ምርቶቻቸው በድርድር ችግር ውስጥ ያሉ አንድ ሰጥተናል ደርድር፣ የምርት እሴታቸው በሠልፍ ውስጥ የሚገኙትን ሁሉንም ልዩ ልዩ ጥንዶች ይቁጠሩ።

ለምሳሌ  

ግቤት

A [] = {2, 5, 6, 3, 15}

ዉጤት

በድርድሩ ውስጥ ምርታቸው የተለያቸው ጥንዶች ብዛት -2

ጥንዶች: (2, 3), (5, 3)

የጭካኔ ኃይል-በድርድር ውስጥ ለምርት ላሉት ቆጠራ ጥንዶች አቀራረብ 1  

በሁሉም ጥንዶች ላይ ብስጭት ፣ እና ከዚያ ያ አካል በድርድሩ ውስጥ ካለ ወይም እንደሌለ ያረጋግጡ። ካለ መልሱን በ 1 ይጨምሩ።

አልጎሪዝም

  1. ተለዋዋጭ አንሶችን በ 0 ያስጀምሩ ፡፡
  2. ከ 0 እስከ n-1 ባለው ክልል ውስጥ ለእኔ ቀለበት ያሂዱ;
    1. በ ‹+ 1 እስከ n-1› ክልል ውስጥ ለ j አንድ ዙር ያሂዱ
      1. አሁን ፣ ከ 0 እስከ n-1 ባለው ክልል ውስጥ ለ k አንድ ዙር ያሂዱ
        1. A [i] * A [j] ከ A [k] ጋር ​​እኩል ከሆነ ታዲያ አንሶቹን በ 1 ይጨምሩ እና ከሉፉ ይሰብሩ።
      2. አትም ans.

C ++ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if (A[i] * A[j] == A[k])
                {
                    ans++;
                    break;
                }
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 5, 6, 3, 15, 30};
    countPairs(A);
    return 0;
}
Number of distinct pairs whose product exists in array is: 4

የጃቫ ፕሮግራም

public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    if (A[i] * A[j] == A[k])
                    {
                        ans++;
                        break;
                    }
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array is: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 5, 6, 3, 15, 30};
    countPairs(A);
  }
}
Number of distinct pairs whose product exists in array is: 4

ድርድር የማን ምርት እንዳለ ለመቁጠር ጥንዶች ውስብስብነት ትንተና

የጊዜ ውስብስብነት ሶስት የጎጆ ቀለበቶችን እየተጠቀምን ነው ፣ ሁሉም መጠን N. ስለዚህ የጊዜ ውስብስብ ነው ኦ (N ^ 3)

ተመልከት
ዱካ ድምር

የቦታ ውስብስብነት ምንም ተጨማሪ ቦታ እየተጠቀምን አይደለም ፣ ስለሆነም የቦታ ውስብስብነት ነው ኦ (1).

ሀሽንግን በመጠቀም-አቀራረብ 2 ምርታቸው በድርድር ውስጥ ለሚገኙ ቆጠራ ጥንዶች  

ዋናዉ ሀሣብ

ሁሉንም የሰልፍ ክፍሎች በሃሽ ሰንጠረዥ ውስጥ እናደርጋለን። ከዚያ በኋላ የጥንድ ምርቱ በሰልፍ ውስጥ ካለ እኛ ሁሉንም ጥንዶች እናካሂዳለን ከዚያም መልሱን በ 1. ጨምር አንድ ምርት በምድቡ ውስጥ ካለ ወይም በቋሚነት በሃሽ ሰንጠረዥ በመፈለግ አለመሆኑን ማረጋገጥ እንችላለን ፡፡

አልጎሪዝም

  1. የሃሽ ጠረጴዛ ያውጁ ፡፡
  2. መልሱን የሚያስቀምጥ ተለዋዋጭ አንስን በ 0 ያስጀምሩ።
  3. ከ 0 እስከ n-1 ባለው ክልል ውስጥ ለእኔ አንድ ዙር ያሂዱ ፡፡
    1. በጄ + 1 እስከ n-1 ባለው ክልል ውስጥ ለ j አንድ ዙር ያሂዱ ፡፡
      1. የ A [i] እና A [j] ምርት በሃሽ ገበታ ውስጥ ካለ ከዚያ አንሶቹን በ 1 ይጨምሩ።
    2. አትም ans.

ለምሳሌ:

ለድርድር ሀ [] = {2, 4, 2, 4, 15, 8, 20}

የሃሽ ሰንጠረዥ እንደዚህ ይመስላል:

የእነሱ ምርቶች በድርድር ውስጥ የሚገኙትን ጥንዶች ይቆጥሩጭንቅላታም መያያዣ መርፌ

C ++ ፕሮግራም

#include <bits/stdc++.h>
using namespace std;
void countPairs(vector<int> &A)
{
    int n = A.size();
    unordered_set<int> hash_table;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        hash_table.insert(A[i]);
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (hash_table.count(A[i] * A[j]) == 1)
            {
                ans++;
            }
        }
    }
    cout << "Number of distinct pairs whose product exists in array is: " << ans << endl;
    return;
}
int main()
{
    vector<int> A = {2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
    return 0;
}
Number of distinct pairs whose product exists in array is: 7

የጃቫ ፕሮግራም

import java.util.*; 
public class Main
{
    static void countPairs(int[] A)
    {
        int n = A.length;
        Set<Integer> hash_table=new HashSet<Integer>();
        int ans = 0;
        for(int i=0;i<n;i++)
        {
            hash_table.add(A[i]);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if(hash_table.contains(A[i]*A[j])==true)
                {
                    ans++;
                }
            }
        }
        System.out.print("Number of distinct pairs whose product exists in array are: "+ans);
    }
  public static void main(String[] args) {
    int[] A={2, 4, 2, 4, 15, 30, 8};
    countPairs(A);
  }
}
Number of distinct pairs whose product exists in array are: 7

ድርድር የማን ምርት እንዳለ ለመቁጠር ጥንዶች ውስብስብነት ትንተና

የጊዜ ውስብስብነት እኛ ሁለት የተጠለፉ ቀለበቶችን እየተጠቀምን ነው ፣ ሁለቱም መጠናቸው N. ስለዚህ የጊዜ ውስብስብነቱ ነው ኦ (N ^ 2).

ተመልከት
የዝናብ ውሃ ማጥመድ

የቦታ ውስብስብነት የሰልፍ ንጣፎችን ለማከማቸት የሃሽ ሰንጠረዥን እንጠብቃለን። ስለዚህ የቦታ ውስብስብነት ነው ኦ (ኤን).

ማጣቀሻዎች