ספירת שלישיות עם סכום נמוך מהערך הנתון  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג Byte סיסקו מצודה Citrix דלתא eBay פייסבוק גולדמן זאקס Google Hulu יבמ אינפוסיס עבודות מתמטיקה מיקרוסופט אורקל פייפאל Qualtrics סמסונג ServiceNow מתיז בצורת ריבוע Tencent טסלה סופר וִיזָה VMware מעבדות וולמארט יאהו Zoho
Akamai מערך Groupon פוסטרים שני מצביעים שתי מצביעים יישומי עבודות

הצהרת בעיה  

נתנו מערך המכיל מספר 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) כי אנחנו לא משתמשים בשום שטח עזר כאן.

הפניות