Колькасць трайнят з сумай, меншай за зададзеную  


Узровень складанасці серада
Часта пытаюцца ў Саман амазонка яблык Bloomberg ByteDance Cisco Citadel Citrix DoorDash eBay facebook Goldman Sachs Google Hulu IBM Infosys Матэматыка Microsoft Аракул PayPal Qualtrics Samsung ServiceNow Splunk Плошча Tencent Цеслы Uber Віза VMware Лабараторыі Walmart Yahoo Zoho
Akamai масіў Groupon Postmates Два паказальнікі Два паказальнікі Працы прыкладанняў

Пастаноўка праблемы  

Мы прывялі масіў, які змяшчае N колькасць элементаў. У дадзеным масіў, Падлічыце колькасць трайнят з сумай, меншай за зададзенае значэнне.

Прыклад  

уваход

а [] = {1, 2, 3, 4, 5, 6, 7, 8}
Сума = 10

выхад

7
Магчымыя тройні: (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5 ), (2,3,4)

уваход

a [] = {3, 7, 9, 1, 2, 5, 11, 4}
Сума = 10

выхад

6
Магчымыя тройні: (3,1,2), (3,1,5), (3,1,4), (3,2,4), (1,2,5), (1,2,4 )

Падыход 1  

Алгарытм

1. Выканайце 3 укладзеныя завесы, выбраўшы ўсе магчымыя тройкі.

2. Ініцыялізаваць вынік = 0.

3. Калі сума элементаў меншая за суму, павялічвайце колькасць.

4. Надрукаваць вынікі ў выглядзе колькасці тройні, якія задавальняюць умове.

Рэалізацыя

Праграма C ++ для падліку тройні з сумай меншай, чым зададзенае значэнне

#include <bits/stdc++.h>
using namespace std;
 
//Main function
int main()
{
    int array[] = {3, 7, 9, 1, 2, 5, 11, 4};
    int N = sizeof(array)/sizeof(array[0]);
    int sum = 10;
    int result = 0;
    //First for loop for selecting first element
    //Second loop for second element
    //Third loop for third element.
    //check for triplets satisfing the condition, and increment result
    for (int i = 0; i < N-2; i++)
    {
       for (int j = i+1; j < N-1; j++)
       {
           for (int k = j+1; k < N; k++)
           {
               if(array[i]+array[j]+array[k] < sum)
                   {
                      result++;
                   }
           }
       }
    }
    cout<<"Number of Triplets found = ";
    cout<<result;
    return 0;
}
Number of Triplets found = 6

Праграма Java для падліку трыплетаў з сумай, меншай за зададзеную

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int sum = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        //First for loop for selecting first element
        //Second loop for second element
        //Third loop for third element.
        //check for triplets satisfing the condition, and increment result
        int result=0;
        for (int i = 0; i < n-2; i++)
        {
           for (int j = i+1; j < n-1; j++)
           {
               for (int k = j+1; k < n; k++)
               {
                   if(a[i]+a[j]+a[k] < sum)
                       {
                          result++;
                       }
               }
           }
        }
        System.out.print("Number of Triplets found = ");
        System.out.println(result);
    }
}
5 6
1 2 3 2 1
Number of Triplets found = 5

Аналіз складанасці

Складанасць часу

O (n * n * n) дзе n - памер дадзенага масіва. Тут мы правяраем усе трыплеты, і калі ўмова праўдзівая, павялічвайце лік выніку.

Глядзіце таксама
Дыяпазон Мінімальны запыт (разлажэнне квадратнага кораня і разрэджаная табліца)

Касмічная складанасць

O (1) таму што мы не выкарыстоўваем тут дапаможную прастору.

Падыход 2  

Алгарытм

1. Адсартаваць дадзены масіў, ініцыялізаваць вынік = 0

2. Перайдзіце ад i да N -2 (N - гэта памер масіва) і вазьміце масіў [i] і першы элемент трыплета.

3. Астатнія два элементы ініцыялізуйце як вуглавыя. масіў [i + 1] і масіў [N-1]

4. рухаць j і k, пакуль яны не сустрэнуцца,

  1. Калі сума большая за зададзеную, перамясціце паказальнік на апошні элемент. (масіў [N-1]).
  2. У адваротным выпадку, калі сума менш, чым дадзеная сума, тады можа быць k -j магчымых элементаў, якія задавальняюць, таму дадайце (kj) у вынік. І перамясціць паказальнік масіва [i + 1].

Крок 5: Раздрукуйце вынік пасля заканчэння цыкла.

Рэалізацыя

Праграма C ++ для падліку тройні з сумай меншай, чым зададзенае значэнне

#include <bits/stdc++.h>
using namespace std;
 
// Main function
int main()
{
    int array[] ={1, 2,3,5,6, 3, 2, 5, 7};//input array
    int N = sizeof(array)/sizeof(array[0]);//size of the input array(N)
    int Sum = 9;//input Sum
    int result = 0;//initilizing count of triplets
    sort(array,array+N);//sorting the input array
    //selecting first element
    for(int i = 0; i < N - 2; i++)
    {
        int j=i+1,k=N-1;//second and third elements as last two elements
        while(j<k)
        {
            // Sum of triplet is greater than or equalto given sum, move to find smaller values
            if(array[i] + array[j] + array[k] >= Sum)
            {
                k--;
            }
            // Sum of triplet is less than given sum
            else
            {
                //for current i and j there can be k-j elements, move j pointer
                result += (k - j);
                j++;
            }
        }
    }
    cout<<"Number of Triplets found = ";
    cout<<result;
}
Number of Triplets found = 14

Праграма Java для падліку трыплетаў з сумай, меншай за зададзеную

import static java.lang.Math.pow;
import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int sum = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        //First for loop for selecting first element
        //Second loop for second element
        //Third loop for third element.
        //check for triplets satisfing the condition, and increment result
        int result=0;
        Arrays. sort(a);//sorting the input array
        //selecting first element
        for(int i = 0; i < n - 2; i++)
        {
            int j=i+1,k=n-1;//second and third elements as last two elements
            while(j<k)
            {
                // Sum of triplet is greater than or equalto given sum, move to find smaller values
                if(a[i] + a[j] + a[k] >= sum)
                {
                    k--;
                }
                // Sum of triplet is less than given sum
                else
                {
                    //for current i and j there can be k-j elements, move j pointer
                    result += (k - j);
                    j++;
                }
            }
        }
        System.out.print("Number of Triplets found = ");
        System.out.println(result);
    }
}
9 9
1 2 3 5 6 3 2 5 7
Number of Triplets found = 14

Аналіз складанасці

Складанасць часу

O (n * n) дзе n - колькасць элементаў, прысутных у масіве. Тут мы выпраўляем адзін элемент трыплета, а затым выкарыстоўваем два метады паказальнікаў, якія запускаюць O (N) у горшым выпадку для аднаго элемента.

Глядзіце таксама
Праверце папярэднюю серыялізацыю бінарнага дрэва

Касмічная складанасць

O (1) таму што мы не выкарыстоўваем тут дапаможную прастору.

Спасылкі