จำนวนสามเท่าที่มีผลรวมน้อยกว่ามูลค่าที่ระบุ

โปรแกรม 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) เพราะเราไม่ได้ใช้พื้นที่เสริมตรงนี้

โปรแกรม 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 คือจำนวนองค์ประกอบที่มีอยู่ในอาร์เรย์ ที่นี่เราแก้ไของค์ประกอบหนึ่งของ triplet จากนั้นใช้สองวิธีตัวชี้ที่เรียกใช้ O (N) ในกรณีที่เลวร้ายที่สุดสำหรับองค์ประกอบหนึ่ง

ความซับซ้อนของอวกาศ

O (1) เพราะเราไม่ได้ใช้พื้นที่เสริมตรงนี้

อ้างอิง