ითვლიან სამკუთხედების რაოდენობას, მოცემული რიცხვის ტოლი პროდუქტით  


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Amazon Cisco Flipkart კულიზა პუბლიკის საპიენტი
Array Hash ორი მაჩვენებელი

პრობლემა "სამმაგი რიცხვის რიცხვი მოცემული რიცხვის ტოლი პროდუქტით" აცხადებს, რომ ჩვენ გვეძლევა მთელი რიგი და რიცხვი m. პრობლემის დებულება ითხოვს, რომ გაიგოთ სამმაგი ჯამური რიცხვი, რომლის პროდუქტი ტოლია m- ს.

მაგალითი  

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

განმარტება

სამეული, რომლებმაც შექმნეს m ტოლი პროდუქტი, არის (1,5,6), (5,2,3) და (1,3,10)

ითვლიან სამკუთხედების რაოდენობას, მოცემული რიცხვის ტოლი პროდუქტითPin

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

განმარტება

სამეული, რომლებმაც შექმნეს პროდუქტი m ტოლია (2,1,10), (4,5,1)

ალგორითმი  

  1. გამოაცხადეთ ა რუკა.
  2. შეინახეთ თითოეული ელემენტის ინდექსი რუკაზე, მასივი.
  3. გამოტოვე 0-ზე.
  4. მასივის ხელახლა გავლა წყობილი მარყუჟის გამოყენებით:
    1. შეამოწმეთ ((arr [i] * arr [j] <= მ) && (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. ჩვენ არ ვაპირებთ გულუბრყვილო მიდგომას გამოვიყენოთ ამ საკითხის გადასაჭრელად, ეს უფრო მეტი დრო გვეღირება. იმის ნაცვლად, რომ მოინახულოთ ტრიპლეტის თითოეული ელემენტი, ჩვენ გამოვიყენებთ ჰაშინგი.

იხილეთ ასევე
პრიმის ალგორითმი

ჩვენ გადავკვეთთ მოცემულ მასივს და თითოეული მასივის ელემენტის ინდექსს შევინახავთ რუქაზე მოცემულ მასივის ელემენტთან ერთად. ეს კეთდება, რადგან მოგვიანებით, ჩვენ ვაპირებთ შეამოწმოთ, არ უნდა განმეორდეს თუ არა ჩვენ მიერ აღმოჩენილი ელემენტი. თუ ელემენტს იგივე ინდექსი აქვს. ეს ნიშნავს, რომ სამკუთხედისთვის ორჯერ არ ჩავთვლით მასივის ერთსა და იმავე ელემენტს.

მასივის გადაკვეთის შემდეგ, ჩვენ გვაქვს მნიშვნელობები ჰეშმაპში. გამომავალი მნიშვნელობის დაყენება 0-ზე. ახლა ჩვენ ვიყენებთ წყობილი მარყუჟის გამოყენებას. რომელშიც ჩვენ ვიღებთ ელემენტს გარე მარყუჟში და შიდა მარყუჟში შემდეგ ვირჩევთ სხვა ელემენტს. შემდეგ ჩვენ ვაპირებთ მესამე ელემენტის გარკვევას. მესამე პირობის გასარკვევად გამოიყენება ყველა პირობა, რომელიც მდგომარეობს ”if” -ში. 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

ჯავის კოდი სამმაგი რიცხვის დასათვლელად, მოცემული რიცხვის ტოლი პროდუქტით  

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სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ვინაიდან ჩვენ გამოვიყენეთ ორი ჩასმული მარყუჟი და Hashmap- ის საშუალებით ვიპოვეთ მესამე ელემენტი. ამრიგად, ამ საძიებო ოპერაციას HashMap ახორციელებს O (1) - ში, რომელიც ადრე O (N) დროში კეთდებოდა გულუბრყვილო მიდგომით. ამრიგად, ეს დაჩქარება ხდება HashMap– ის გამო.

იხილეთ ასევე
ყველა თანამშრომლის ქვეშ იპოვნეთ თანამშრომლების რაოდენობა

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. რადგან ჩვენ ყველა ელემენტს შევინახავთ რუქაში. სივრცის სირთულე ხაზოვანია.