Verilmiş bir array N elementdən A. Tapşırıq, verilmiş bir sıra iki elementinin məhsulu olacağı şəkildə massivdə mövcud olan ən böyük S sayını tapmaqdır (S cütə daxil edilə bilməz. Həm də cütlük fərqli indekslərdən olmalıdır). Əgər belə bir cüt yoxdursa, onda -1 yazdırın.
Mündəricat
misal
Input:
6 10 2 2 4 30 35
Çıxış:
4
Kobud qüvvə: Array-da ən yaxşı məhsulla cüt tapmaq üçün yanaşma 1
Dizidəki hər cüt cütü götürə bilərik və məhsulun massivdə olub olmadığını yoxlaya bilərik və bütün bu etibarlı cütlər arasında ən yüksək məhsulu seçəcəyik.
Alqoritm
- Dizini azalan qaydada çeşidləyin.
- Dəyişən “ans” ı -1 ilə başlayın.
- 0-dan n-1 aralığında I üçün bir döngə çalıştırın
- J üçün i + 1 - n-1 aralığında bir döngə çalıştırın
- J + 1-dən n-1 aralığında k üçün bir döngə işlədin
- Arr [k] arr [i] * arr [j] -ə bərabərdirsə, ans = arr [k] dəyərini yeniləyin və döngədən çıxın.
- J + 1-dən n-1 aralığında k üçün bir döngə işlədin
- J üçün i + 1 - n-1 aralığında bir döngə çalıştırın
- Ans çap et.
Həyata keçirilməsi
Dizidəki ən böyük məhsula sahib cüt tapmaq üçün C ++ proqramı
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr.begin(),arr.end());
int ans=-1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(arr[k]==arr[i]*arr[j])
{
ans=arr[k];
break;
}
}
}
}
cout<<ans<<endl;
return 0;
}
6 10 2 2 4 30 35
4
Dizidəki ən böyük məhsula sahib cüt tapmaq üçün JAVA proqramı
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
Arrays.sort(arr);
int ans=-1;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(arr[k]==arr[i]*arr[j])
{
ans=arr[k];
break;
}
}
}
}
System.out.println(ans);
}
}
9 35 7 5 8 2 2 56 3 1
56
Dizidəki ən böyük məhsula sahib cüt tapmaq üçün mürəkkəblik analizi
Zaman mürəkkəbliyi
N ölçülü 3 iç içə döngə işlədirik, ümumi zaman mürəkkəbliyimizdir O (N ^ 3).
Kosmik Mürəkkəblik
Yalnız 1 əlavə dəyişən götürdük, buna görə daimi bir yer mürəkkəbliyimiz var O (1).
Hashingdən istifadə: Array-da ən yaxşı məhsul ilə cüt tapmaq üçün 2 yanaşma
Əsas fikir
bütün element elementlərini bir elementin O (1) vaxtında olub olmadığını yoxlamaq üçün bir hash cədvəlində saxlaya bilərik. İndi hər bir elementi, məhsulu elementə bərabər olan bir cüt hissəsinin massivdə olub olmadığını yoxlaya bilərik.
Ayrıca, elementin aralığı 0 ilə 10 ^ 5 arasındadır, buna görə sadəcə üçün bir sıra istifadə edə bilərik sükut masa.
Cari elementin mükəmməl bir kvadrat və ya 1-ə bərabər olub olmadığını ayrı-ayrılıqda yoxlamalıyıq.
Alqoritm
- Bir sıra istifadə edərək bir hash masa yaradın və bütün array elementlərini içərisində saxlayın.
- Dizini azalan sırada sıralayın.
- 0-dan n-1 aralığında I üçün bir döngə çalıştırın
- J üçün sqrt (arr [i]) aralığında 2 üçün bir döngə işlədin
- J arr [i] ilə bölünürsə, başqa bir element k = arr [i] / j başlanğıc edin.
- J və k bərabərdirsə, j sayı 1-dən çox olarsa arr [i] cavabdır və hər iki döngədən çıxır.
- J və k bərabər deyilsə, not elementində hər iki elementin olub olmadığını yoxlayın, bəli əgər arr [i] cavabdır və hər iki döngədən qopun.
- J üçün sqrt (arr [i]) aralığında 2 üçün bir döngə işlədin
- Cavab tapmışıqsa, başqa bir şəkildə çap et -1.
Məsələn:
Giriş massivi = {10, 2, 2, 4, 30, 35}
Sonra hash cədvəli belə görünür:
Sağ sütunda ədədi, sağ sütunda isə onların tezliyini massivdə göstərir.
Həyata keçirilməsi
Dizidəki ən böyük məhsula sahib cüt tapmaq üçün C ++ proqramı
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> m(100001,0);
for (int i = 0; i < n; i++)
{
cin >> a[i];
m[a[i]]++;
}
sort(a.begin(), a.end(),greater<int>());
bool flag = false;
for (int i = 0; i<n; i++)
{
if (a[i] == 1)
{
if (m[a[i]] >= 3)
{
cout << a[i] << endl;
flag = true;
break;
}
else
{
continue;
}
}
for (int divisor_1 = 2; divisor_1 * divisor_1 <= a[i]; divisor_1++)
{
if (a[i] % divisor_1 == 0)
{
int divisor_2 = a[i] / divisor_1;
if (divisor_1 == divisor_2)
{
if (m[divisor_1] > 1)
{
cout << a[i] << endl;
flag = true;
break;
}
}
else
{
if ((m[divisor_1]>0) and (m[divisor_2]>0))
{
cout << a[i] << endl;
flag = true;
break;
}
}
}
}
if (flag)
{
break;
}
}
if (flag == false)
{
cout << "-1" << endl;
}
return 0;
}
11 22 72 9 8 11 33 123 21 45 10 5
72
Dizidəki ən böyük məhsula sahib cüt tapmaq üçün Java proqramı
import java.util.*;
public class Main
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a=new int[n];
int[] m=new int[100001];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
m[a[i]]++;
}
Arrays.sort(a);
boolean flag = false;
for (int i = n-1; i>=0; i--)
{
if (a[i] == 1)
{
if (m[a[i]] >= 3)
{
System.out.println(a[i]);
flag = true;
break;
}
else
{
continue;
}
}
for (int divisor_1 = 2; divisor_1 * divisor_1 <= a[i]; divisor_1++)
{
if (a[i] % divisor_1 == 0)
{
int divisor_2 = a[i] / divisor_1;
if (divisor_1 == divisor_2)
{
if (m[divisor_1] > 1)
{
System.out.println(a[i]);
flag = true;
break;
}
}
else
{
if ((m[divisor_1]>0) && (m[divisor_2]>0))
{
System.out.println(a[i]);
flag = true;
break;
}
}
}
}
if (flag)
{
break;
}
}
if (flag == false)
{
System.out.println("-1");
}
}
}
11 22 72 9 8 11 33 123 21 45 10 5
72
Mürəkkəblik təhlili
Zaman mürəkkəbliyi
Ən pis vəziyyətdə bütün massivi təkrarlayırıq və hər element üçün sqrt (N) üçün bir döngə işlədirik. Beləliklə, ümumi vaxt mürəkkəbliyi O (N ^ sqrt (N)).
Kosmik mürəkkəblik
Məkan mürəkkəbliyi olduğu üçün bir hash masası saxlamalıyıq O (N).
