与えられた数に等しい積を持つトリプレットの数を数えます


難易度 ミディアム
よく聞かれる アコライト Amazon (アマゾン) Cisco フリップカート クリザ Publicis Sapient
配列 ハッシュ XNUMXつのポインター

「積が与えられた数に等しいトリプレットの数を数える」という問題は、整数配列と数が与えられていることを示しています m。 問題ステートメントは、積がmに等しいのトリプレットの総数を見つけるように求めています。

arr[] = {1,5,2,6,10,3}
m=30
3

説明

mに等しい積を形成したトリプレットは、(1,5,6)、(5,2,3)、および(1,3,10)です。

与えられた数に等しい積を持つトリプレットの数を数えます

arr[] = {2,4,5,1,10}
m=20
2

説明

mに等しい積を形成したトリプレットは(2,1,10)、(4,5,1)です。

アルゴリズム

  1. 宣言する 地図.
  2. 各要素のインデックスをトラバースしてマップに保存します 配列.
  3. 出力を0に設定します。
  4. ネストされたループを使用して配列を再度トラバースします。
    1. if((arr [i] * arr [j] <= m)&&(arr [i] * arr [j]!= 0)&&(m%(arr [i] * arr [j])== 0 ))。
      1. これが当てはまる場合は、m /(arr [i] * arr [j])を見つけて、マップで検索します。
    2. また、見つかったXNUMX番目の要素が現在のXNUMXつの要素(arr [i]とarr [j])と等しくないことも確認してください。
      1. 条件が満たされている場合は、出力の数を1つ増やします。
  5. 出力を返します。

説明

私たちの仕事は、積が与えられた数mに等しくなければならないトリプレットを見つけることです。 この問題を解決するために単純なアプローチを使用するつもりはありません。より多くの時間がかかります。 トリプレットの各要素を選択するのではなく、 ハッシング.

指定された配列をトラバースし、各配列要素のインデックスを指定された配列要素とともにマップに格納します。 これが行われているのは、後で、見つかった要素を繰り返さないかどうかを確認するためです。 要素のインデックスが同じ場合。 これは、トリプレットに対して同じ配列要素をXNUMX回カウントしないことを意味します。

配列を走査した後、ハッシュマップに値があります。 outputの値を0に設定します。次に、ネストされたループを使用します。 外側のループで要素を取得し、次に内側のループで別の要素を選択します。 次に、XNUMX番目の要素を見つけます。 'ifステートメント'にあるすべての条件は、XNUMX番目の要素を見つけるために使用されます。 arr [i] * arr [j]を実行した後、見つける必要があるのはXNUMX番目の要素だけです。 したがって、簡単に言えば、a * b * c =m⇒の場合、c = m / a * bです。

次に、1番目の要素を確認します。マップに表示されている場合は、それが見つかったことを意味します。 見つけた要素がトリプレットの現在のXNUMXつの要素と等しくないかどうかを確認する必要があります。 また、現在のインデックスは以前に繰り返されるべきではありませんでした。 すべての条件が満たされている場合は、出力の数をXNUMXつ増やすだけです。これは、XNUMXつ以上のトリプレットがあることを意味します。 そして最後に単に出力を返します。

与えられた数に等しい積を持つトリプレットの数を数えるC ++コード

#include<iostream>
#include<unordered_map>
using namespace std;

int getProductTriplets(int arr[], int n, int m)
{
    unordered_map<int, int> numindex;
    for (int i = 0; i < n; i++)
        numindex[arr[i]] = i;

    int output = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
            {
                int third = m / (arr[i] * arr[j]);
                auto it = numindex.find(third);

                if (third != arr[i] && third != arr[j]&& it != numindex.end() && it->second > i&& it->second > j)
                    output++;
            }
        }
    }
    return output;
}
int main()
{
    int arr[] = {1,5,2,6,10,3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 30;

    cout <<"Total product triplets are: "<<getProductTriplets(arr, n, m);
    return 0;
}
Total product triplets are: 3

与えられた数に等しい積を持つトリプレットの数を数えるJavaコード

import java.util.HashMap;

class TripletProductPair
{
    public static int getProductTriplets(int arr[], int n, int m)
    {
        HashMap<Integer, Integer> numindex = new HashMap<Integer, Integer>(n);
        for (int i = 0; i < n; i++)
            numindex.put(arr[i], i);

        int output = 0;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {

                if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
                {
                    int third = m / (arr[i] * arr[j]);

                    numindex.containsKey(third);
                    if (third != arr[i] && third != arr[j]&& numindex.containsKey(third) && numindex.get(third) > i && numindex.get(third) > j)
                    {
                        output++;
                    }
                }
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,5,2,6,10,3};
        int m = 30;
        System.out.println("Total product triplets are: "+getProductTriplets(arr, arr.length, m));
    }
}
Total product triplets are: 3

複雑さの分析

時間の複雑さ

オン2where 「n」 配列内の要素の数です。 1つのネストされたループを使用し、Hashmapを使用してXNUMX番目の要素を検索したためです。 したがって、この検索操作は、以前は単純なアプローチでO(N)時間に実行されていたO(XNUMX)のHashMapによって実行されています。 したがって、このスピードアップはHashMapによるものです。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 すべての要素をマップに保存するためです。 空間の複雑さは線形です。