Pուգակցվեք տվյալ ապրանքի հետ


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են 24 * 7 նորարարության լաբորատորիաներ Amazon Ավալարա Quora Roblox
Դասավորություն Խանգարել Մաթեմատիկա

«Givenույգ տրված ապրանքի հետ» խնդրի մեջ նշվում է, որ ձեզ տրվում է ան ամբողջ թիվ դասավորություն և «x» թիվը: Որոշեք, արդյոք զանգվածը բաղկացած է զույգից, որի արտադրանքը հավասար է 'x' տրված մուտքային զանգվածում:

Օրինակ

[2,30,12,5]
x = 10
Yes, it has Product Pair

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

Pուգակցվեք տվյալ ապրանքի հետ

Այստեղ 2-ը և 5-ը այն տարրերն են, որոնց արտադրանքը հավասար է 10-ի, այսինքն x- ին:

[10,30,12,50]
x = 40
No, it does not have a Product Pair.

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

Rayանգվածում չկա նման զույգ, որի արտադրյալը հավասար է x- ին, այսինքն ՝ 40-ին:

[20,3,12,5]
x = 100
Yes, it has a Product Pair.

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

Այստեղ զանգվածում 20-ը և 5-ը կազմում են մի զույգ, որի արտադրանքը հավասար է x- ի, այսինքն `100-ի:

Ալգորիթմ `պարզելու համար, արդյոք տվյալ ապրանքի հետ airույգ գոյություն ունի

  1. Հայտարարել ա HashSet.
  2. Ստուգեք զանգվածի երկարությունը, եթե տրված է առնվազն 2 արժեք:
    1. Եթե ​​ոչ, կեղծ վերադարձիր:
  3. Ժամանակ ես <n.
    1. Ստուգեք, արդյոք զանգվածի տարրերից մեկը հավասար է 0-ի
      1. Եթե ​​x- ին տրվում է նաև 0, ապա վերադարձիր true:
    2. Ստուգեք, արդյոք x- ը կարելի է բաժանել arr- ի որևէ տարրից և տալիս է 0 մնացորդը:
      1. Եթե ​​HashSet- ը պարունակում է (x / arr [i]), ապա վերադարձիր true:
      2. Ավելացրեք arr [i] -ը HashSet- ին:
  4. Վերադարձեք կեղծ:

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

Մեզ տրված է մի խնդիր, որում տրված են զանգված և թիվ: Դրանից հետո մենք պետք է պարզենք, արդյոք մուտքային զանգվածում գոյություն ունի որևէ զույգ, որն x հավասար է Ապրանքին: Մենք պատրաստվում ենք օգտագործել ծիծաղել լուծել այս խնդիրը: Պարզելու համար տվյալ արտադրանքի հետ զանգվածում գոյություն ունեցող արժեքը: Մենք x- ը բաժանում ենք arr [i] - ով և ստուգում, արդյոք մնացորդը 0. է: Եթե պարզվում է, որ 0 է, ապա մենք ստուգելու ենք, արդյոք x / arr [i] գոյություն ունի HashSet- ում: Եթե ​​դա գոյություն ունի, մենք կվերադառնանք իրական: Եթե ​​ոչ, պարզապես այդ տարրերի զանգվածը ավելացրեք HashSet- ի մեջ `հետագա անցման համար:

Մեզ նաև տրված է պայման, որը պետք է հստակ ստուգի զրոյական Ապրանքը: Եթե ​​մեր x արժեքը տրվի 0, մենք կստուգենք, թե զանգվածի տարրերից որևէ մեկը 0 է, իսկ եթե դա այդպես է, ապա մենք կվերադառնանք ճշմարիտ, քանի որ ցանկացածի վրա բազմապատկած զրոն միշտ զրո է:

Եկեք օրինակ վերցնենք և հասկանանք սա.

arr [] = {10,20,9,40}, X = 90

i = 0, arr [i] = 10,

Մենք ստուգելու ենք արդյոք arr [i] - ը հավասար է 0-ի, բայց այս զանգվածում նույնիսկ մեկ տարր էլ 0 չէ, ուստի այն չի կատարվի որևէ կրկնությամբ:

Մենք այստեղ պարզապես ստուգելու ենք, եթե x% arr [i] = = 0, եթե այն անցնում է, ապա մենք ստուգելու ենք x / arr [i] դրված է, թե ոչ:

90% 10 == 0 ճիշտ է, իսկ 90/10 = 9 դեռ HashSet- ում չէ:

Այսպիսով, մենք հավաքածուի մեջ կավելացնենք arr [i] = 10:

90% 20 == 0-ը կեղծ է, և ոչինչ չի պատահում

90% 9 == 0 ճիշտ է, և 90/9 = 10 առկա է HashSet- ում, ինչպես մենք արդեն տեղադրեցինք HashSet- ում:

Այսպիսով, դա նշանակում է, որ մենք ունենք Ապրանքի զույգ ՝ որպես զանգված 9 և 10, և վերադարձնում է true և տպում

Արդյունք. «Այո, այն ունի արտադրանքի զույգ»:

C ++ կոդ ՝ տվյալ ապրանքի հետ զույգ գտնելու համար

#include<iostream>
#include<unordered_set>
using namespace std;
bool getProduct (int arr[], int n, int x)
{
  if (n < 2)
    return false;

  unordered_set<int> s;

  for (int i=0; i<n; i++)
  {
    if (arr[i] == 0)
    {
    if (x == 0)
      return true;
    else
      continue;
    }
    if (x%arr[i] == 0)
    {
      if (s.find(x/arr[i]) != s.end())
                return true;

      s.insert(arr[i]);
    }
  }
  return false;
}
int main()
{
  int arr[] = {10, 20, 9, 40};
  int x = 90;
  int n = sizeof(arr)/sizeof(arr[0]);
  getProduct (arr, n, x)? cout << "Yes, it has Product Pair\n":cout << "No, it does not have Product Pair";
  return 0;
}
Yes, it has Product Pair

Java կոդ ՝ տվյալ ապրանքի հետ airույգ գտնելու համար

import java.util.HashSet;

class pairX
{
    public static boolean getProduct (int arr[], int n, int x)
    {
        HashSet<Integer> mySet = new HashSet<>();

        if(n < 2)
            return false;

        for(int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
            {
                if(x == 0)
                    return true;
                else
                    continue;
            }
            if(x % arr[i] == 0)
            {
                if(mySet.contains(x / arr[i]))
                    return true;

                mySet.add(arr[i]);
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = {10, 20, 9, 40};
        int x = 90;
        int n = arr.length;

        if(getProduct (arr, n, x))
            System.out.println("Yes, it has Product Pair");
        else
            System.out.println("No, it does not have Product Pair");
    }
}
Yes, it has Product Pair

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

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք օգտագործել ենք HashSet, մենք կարողացանք ներդնել, ջնջել և որոնել O (1) ժամանակում: Դրա շնորհիվ մենք կարողացանք հասնել գծային ժամանակի բարդության:

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Եթե ​​բոլոր տարրերը պահվեն HashSet- ում, ապա այն կունենա N պայմաններ: Դա կարժենա մեզ գծային տարածություն: Քանի որ, երբ մուտքն ավելանում է, տարածությունն ավելանում է: