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

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;
}

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