Mümkün üçbucaqları sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon LinkedIn Wipro
Geyim RiyaziyyatBaxılıb 755

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Mümkün üçbucaqların sayında bir verdik array n müsbət tam ədədi. Üçbucağın tərəfləri kimi massivin üç fərqli elementindən istifadə edərək yarana bilən üçbucaqların sayını tapın.

Qeyd: Üçbucağın şərti üçbucağın iki tərəfinin cəmi üçüncü tərəfdən daha böyükdür.

misal

Input

arr [] = {2, 3, 4, 5, 6, 7}

Buraxılış

13

Izahat

Bütün mümkün üçqat

{2, 3, 4}, {2, 4, 5}, {2, 5, 6}, {2, 6, 7}, {3, 4, 5}, {3, 4, 6}, {3 , 5, 6}, {3, 5, 7}, {3, 6, 7}, {4, 5, 6}, {4, 5, 7}, {4, 6, 7}, {5, 6 , 7}

Mümkün üçbucaqları saymaq üçün alqoritm

İndi problem ifadəsini aydın şəkildə başa düşürük. Beləliklə, nəzəriyyəyə çox vaxt sərf etmədən birbaşa serialdakı üçbucaqların sayını tapmaq üçün istifadə olunan alqoritmə keçirik.

a. Verilən massivi artan qaydada çeşidləyin.

b. İ, j və k üç mövqeyi tutun

  • I element üçün. i 0 dan n - 3 arasındadır.
  • ikinci element üçün j. i i + 1-dən n - 2-ə qədərdir.
  • üçüncü element üçün k. k i + 2 ilə n -1 arasındadır.

c. K hərəkəti ilə c və c cərəyanının cəmindən kiçik olan ən sağ elementi tapın.
d. K - j - 1 cərəyan i və j üçün üçbucaqların sayıdır.
e. Saya əlavə edin və i, j artırın.

Həyata keçirilməsi

Mümkün üçbucaqları saymaq üçün C ++ proqramı

#include <bits/stdc++.h>
using namespace std;
 
int compare(const void* a, const void* b)
{  
    return *(int*)a > *(int*)b; 
}
int TrianglesCount(int array[], int n)
{
    qsort(array,n,sizeof(array[0]),compare);
    int count = 0;
    for(int i = 0; i < n-2; ++i)
    {
        for (int j = i+1; j < n; ++j)
        {
            int k = j+1;
            while (k < n && array[i] + array[j] > array[k])
            {
               k = k + 1;
            }
            count=count+k-j-1;
        }
    }
    return count;
}
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"Total number of Triangles can be formed is = "<<TrianglesCount(input_array,n);
    return 0;
}

Mümkün üçbucaqları saymaq üçün Java proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int TrianglesCount(int arr[], int n) 
    { 
        Arrays.sort(arr);
        int count = 0; 
        for (int i = 0; i < n - 2; ++i) { 
            int k = i + 2; 
            for (int j = i + 1; j < n; ++j) { 
                while (k < n && arr[i] + arr[j] > arr[k]) 
                    ++k; 
                if (k > j) 
                    count += k - j - 1; 
            } 
        } 
        return count; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = TrianglesCount(arr,n);
        System.out.println("Total number of Triangles can be formed is = " + ans);
    } 
}
5
2 3 4 5 6
Total number of Triangles can be formed is = 7

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2) burada n - verilən massivdə mövcud olan elementlərin sayı. Zamanın mürəkkəbliyi 3 iç içə döngə olduğundan daha çox görünür. K-nin ən xarici dövrədə yalnız bir dəfə başlandığı müşahidə edilə bilər. Ən daxili döngə ən xarici döngənin hər təkrarlanması üçün ən çox O (n) dəfə icra olunur, çünki k i + 2-dən başlayır və j-nin bütün dəyərləri üçün n-ə qalxır. Buna görə zaman mürəkkəbliyi O (n ^ 2) -dir.

Kosmik Mürəkkəblik

O (1) çünki bizi daimi kosmik mürəkkəbliyə aparan bir neçə dəyişən yaradırıq.

References

Crack Sistemi Dizayn Müsahibələri
Translate »