ການນັບ ຈຳ ນວນເລກສາມມີຜົນລວມ ໜ້ອຍ ກວ່າມູນຄ່າທີ່ໄດ້ຮັບ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco Citadel Citrix DoorDash eBay ເຟສບຸກ Goldman Sachs ກູໂກ Hulu IBM Infosys ວຽກຄະນິດສາດ Microsoft Oracle PayPal Qualtrics Samsung ServiceNow ແຕກອອກ Square Tencent Tesla Uber ສະແດງໃຫ້ເຫັນ VMware ຫ້ອງທົດລອງ Walmart Yahoo Zoho
Akamai Array Groupon ເພື່ອນຮ່ວມງານ ສອງຕົວຊີ້ ສອງຈຸດ ສະ ໝັກ ວຽກ

ຖະແຫຼງການບັນຫາ  

ພວກເຮົາໄດ້ມອບແຖວທີ່ປະກອບດ້ວຍ ຈຳ ນວນອົງປະກອບ N. ໃນການໃຫ້ array, ນັບ ຈຳ ນວນເລກສາມມີ ຈຳ ນວນນ້ອຍກ່ວາມູນຄ່າທີ່ໄດ້ມອບໃຫ້.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ

a [] = {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. ຖ້າຜົນລວມຂອງອົງປະກອບນ້ອຍກວ່າ Sum, ຕົວເລກເພີ່ມ.

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 Program ສຳ ລັບນັບສາມເທົ່າດ້ວຍຜົນລວມ ໜ້ອຍ ກວ່າມູນຄ່າທີ່ໄດ້ຮັບ

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. Iterate ຈາກ i ເຖິງ N -2 (N ແມ່ນຂະ ໜາດ ຂອງຂບວນ), ແລະເອົາ array [i] ແລະອົງປະກອບ ທຳ ອິດຂອງ triplet.

3. ເລີ່ມຕົ້ນສອງອົງປະກອບອື່ນເປັນສ່ວນປະກອບແຈ. array [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 Program ສຳ ລັບນັບສາມເທົ່າດ້ວຍຜົນລວມ ໜ້ອຍ ກວ່າມູນຄ່າທີ່ໄດ້ຮັບ

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) ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ໄດ້ໃຊ້ບ່ອນຊ່ວຍຫຍັງຢູ່ທີ່ນີ້.

ເອກະສານ