Հաշվի՛ր տրված թվին հավասար արտադրանքով եռյակների քանակը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Ակոլիտ Amazon Cisco Flipkart Կուլիզա Publicis Sapient
Դասավորություն Խանգարել Երկու ցուցիչ

«Հաշվի՛ր եռապատկերի թիվը արտադրյալով հավասար տրված թվին» խնդիրը ասում է, որ մեզ տրվում է ամբողջ զանգված և թիվ 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. Ստուգեք արդյոք ((arr [i] * arr [j] <= m) && (arr [i] * arr [j]! = 0) && (m% (arr [i] * arr [j]) == 0 ))
      1. Եթե ​​պարզվում է, որ դա ճիշտ է, ապա պարզեք m / (arr [i] * arr [j]) և որոնեք այն քարտեզում:
    2. Ստուգեք նաև, որ մեր գտած երրորդ տարրը հավասար չէ ներկայիս երկու տարրերին (arr [i] և arr [j]):
      1. Եթե ​​պայմանը բավարարում է, ապա արտադրանքի քանակը ավելացրեք 1-ով:
  5. Վերադարձի արդյունքը:

բացատրություն

Մեր խնդիրն է պարզել այն եռյակները, որոնց արտադրյալը պետք է հավասար լինի տրված m թվին: Մենք չենք պատրաստվում օգտագործել միամիտ մոտեցում այս հարցը լուծելու համար, դա մեզ համար ավելի շատ ժամանակ է պահանջում: Փոխանակ այցելելու եռյակի յուրաքանչյուր տարր ընտրելու փոխարեն, մենք կօգտագործենք Հեշինգ.

Մենք անցնելու ենք տրված զանգվածը և յուրաքանչյուր զանգվածի տարրերի ցուցիչը պահելու ենք քարտեզում `տվյալ զանգվածի տարրի հետ միասին: Դա արվում է, քանի որ հետագայում մենք փորձելու ենք ստուգել, ​​արդյոք մեր գտած տարրը չպետք է կրկնվի: Եթե ​​տարրը նույն ցուցանիշն ունի: Սա նշանակում է, որ եռակի համար մենք երկու անգամ չենք հաշվում նույն զանգվածի տարրը:

Rayանգվածի անցումից հետո մենք արժեքներ ունենք hashmap- ում: Արդյունքի արժեքը դրեք 0-ի վրա: Այժմ մենք մտադիր ենք օգտագործել տեղադրված օղակ: Որում մենք վերցնում ենք տարր արտաքին օղակում և ներքին օղակում հաջորդը ընտրում ենք մեկ այլ տարր: Դրանից հետո մենք պարզելու ենք երրորդ տարրը: Երրորդ տարրը պարզելու համար օգտագործվում է «if statement» - ի մեջ պարունակվող բոլոր պայմանները: Arr [i] * arr [j] անելուց հետո մեզ մնում է գտնել միայն երրորդ տարրը: Այսպիսով, պարզ գրության վրա, եթե a * b * c = m ⇒ ապա c = m / a * b:

Դրանից հետո ստուգեք երրորդ տարրը, եթե այն ներկայացված է քարտեզում, նշանակում է, որ մենք այն գտել ենք: Մենք պարզապես պետք է ստուգենք, թե արդյոք մեր գտած տարրը չպետք է հավասար լինի եռյակի ներկայիս երկու տարրերին: Բացի այդ, ընթացիկ ցուցանիշը նախկինում չպետք է կրկնվեր: Եթե ​​բոլոր պայմանները բավարարված են, ապա մենք պարզապես ավելացնում ենք արտադրանքի քանակը 1-ով: Սա նշանակում է, որ մենք ունենք մեկ կամ մի քանի եռյակ: Հետո վերջապես պարզապես վերադարձրեք արդյունքը:

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

Բարդության վերլուծություն

Timeամանակի բարդություն

Վրա2որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք օգտագործել ենք երկու տեղադրված օղակ և օգտագործել Hashmap- ը երրորդ տարրը որոնելու համար: Այսպիսով, որոնման այս գործողությունը կատարվում է HashMap- ի կողմից O (1) –ում, որը նախկինում արվում էր O (N) ժամանակում ՝ միամիտ մոտեցմամբ: Այսպիսով, այս արագացումը HashMap- ի պատճառով է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք բոլոր տարրերը կպահպանենք քարտեզում: Տիեզերական բարդությունը գծային է: