Броји број тројки са производом једнаким задатом броју


Ниво тешкоће Средњи
Често питани у Аццолите амазонка Цисцо Флипкарт Кулиза Публицис Сапиент
Ред Хасх Тво Поинтер

Проблем „Броји број тројки са производом једнаким задатом броју“ наводи да смо добили целобројни низ и број m. Изјава о проблему тражи да се сазна укупан број тројки са производом једнаким м.

Пример

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

Објашњење

Тројке које су створиле производ једнак м су (1,5,6), (5,2,3) и (1,3,10)

Броји број тројки са производом једнаким задатом броју

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

Објашњење

Тројке које су створиле производ једнак м су (2,1,10), (4,5,1)

Алгоритам

  1. Изјавите а Мапа.
  2. Спремите индекс сваког елемента на мапу преласком по поредак.
  3. Поставите излаз на 0.
  4. Прелазак низом поново помоћу угнежђене петље:
    1. Проверите да ли је ((арр [и] * арр [ј] <= м) && (арр [и] * арр [ј]! = 0) && (м% (арр [и] * арр [ј]) == 0 )).
      1. Ако се утврди да је ово тачно, сазнајте м / (арр [и] * арр [ј]) и претражите га на мапи.
    2. Такође проверите да ли трећи елемент који смо пронашли није једнак тренутна два елемента (арр [и] и арр [ј]).
      1. Ако услов задовољава, повећајте број излаза за 1.
  5. Повратни излаз.

Објашњење

Наш задатак је да откријемо тројке чији производ треба да буде једнак датом броју м. Нећемо користити наиван приступ да бисмо решили ово питање, кошта нас више времена. Уместо да посећујемо бирајући сваки елемент триплета, ми ћемо га користити Хасхинг.

Прећи ћемо преко датог низа и похранити индекс сваког елемента низа на мапу заједно са датим елементом низа. То се ради јер ћемо касније проверити да ли елемент који смо пронашли не треба понављати. Ако елемент има исти индекс. То значи да исти елемент низа не рачунамо два пута за триплет.

Након преласка низа, имамо вредности у хеш-мапи. Поставите вредност излаза на 0. Сада ћемо користити угнежђену петљу. У којој узимамо елемент у спољној петљи, а у унутрашњој петљи следећи изаберите други елемент. Тада ћемо открити трећи елемент. Сви услови који леже у „иф изјави“ користе се за откривање трећег елемента. Након извршавања арр [и] * арр [ј] све што требамо пронаћи је трећи елемент. Дакле, на једноставној напомени, ако је а * б * ц = м ⇒, тада је ц = м / а * б.

Затим проверите да ли је трећи елемент, ако се налази на мапи, значи да смо га пронашли. Морамо само да проверимо да ли елемент који смо пронашли не би требало да буде једнак са тренутна два елемента триплета. Такође, тренутни индекс није требало раније понављати. Ако су сви услови задовољени, онда само повећавамо број излаза за 1. То значи да имамо једну или више тројки. Затим напокон једноставно вратите излаз.

Ц ++ код за бројање броја тројки са производом једнаким задатом броју

#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

Јава код за бројање броја тројки са производом једнаким задатом броју

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

Анализа сложености

Сложеност времена

На2где „Н“ је број елемената у низу. Пошто смо користили две угнежђене петље и користили Хасхмап за тражење трећег елемента. Дакле, ову операцију претраживања врши ХасхМап у О (1), што је претходно било изведено у О (Н) времену у наивном приступу. Стога је ово убрзање због ХасхМап-а.

Сложеност простора

Он) где „Н“ је број елемената у низу. Јер ћемо све елементе сачувати на мапи. Сложеност простора је линеарна.