Рубрики

Подсчет триплетов с суммой меньше заданного значения

Дан массив различных целых чисел и значение суммы. Найти количество триплетов с суммой, меньшей, чем заданное значение суммы. Ожидаемая временная сложность O (n 2 ).

Примеры:

Input : arr[] = {-2, 0, 1, 3}
        sum = 2.
Output : 2
Explanation :  Below are triplets with sum less than 2
               (-2, 0, 1) and (-2, 0, 3) 

Input : arr[] = {5, 1, 3, 4, 7}
        sum = 12.
Output : 4
Explanation :  Below are triplets with sum less than 12
               (1, 3, 4), (1, 3, 5), (1, 3, 7) and 
               (1, 4, 5)

Простое решение состоит в том, чтобы запустить три цикла, чтобы рассмотреть все триплеты один за другим. Для каждого триплета сравните суммы и количество приращений, если сумма триплета меньше заданной суммы.

C ++

// Простая программа на C ++ для подсчета триплетов с меньшей суммой
// чем данное значение
#include<bits/stdc++.h>

using namespace std;

  

int countTriplets(int arr[], int n, int sum)

{

    // Инициализировать результат

    int ans = 0;

  

    // Зафиксируем первый элемент как A [i]

    for (int i = 0; i < n-2; i++)

    {

       // Исправить второй элемент как A [j]

       for (int j = i+1; j < n-1; j++)

       {

           // Теперь ищем третий номер

           for (int k = j+1; k < n; k++)

               if (arr[i] + arr[j] + arr[k] < sum)

                   ans++;

       }

    }

  

    return ans;

}

  
// Драйвер программы

int main()

{

    int arr[] = {5, 1, 3, 4, 7};

    int n = sizeof arr / sizeof arr[0];

    int sum = 12;

    cout << countTriplets(arr, n, sum) << endl;

    return 0;

}

Джава

// Простая Java-программа для подсчета триплетов с меньшей суммой
// чем данное значение

  

class Test

{

    static int arr[] = new int[]{5, 1, 3, 4, 7};

      

    static int countTriplets(int n, int sum)

    {

        // Инициализировать результат

        int ans = 0;

       

        // Зафиксируем первый элемент как A [i]

        for (int i = 0; i < n-2; i++)

        {

           // Исправить второй элемент как A [j]

           for (int j = i+1; j < n-1; j++)

           {

               // Теперь ищем третий номер

               for (int k = j+1; k < n; k++)

                   if (arr[i] + arr[j] + arr[k] < sum)

                       ans++;

           }

        }

       

        return ans;

    }

      

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        int sum = 12

        System.out.println(countTriplets(arr.length, sum));

    }

}

Python 3

# Простая программа на Python 3 для подсчета триплетов с меньшей суммой
# чем заданное значение
#include <бит / STDC ++. ч>

def countTriplets(arr, n, sum):

  

    # Инициализировать результат

    ans = 0

  

    # Исправить первый элемент как A [i]

    for i in range( 0 ,n-2):

      

        # Исправить второй элемент как A [j]

        for j in range( i+1 ,n-1):

      

            # Теперь ищите третий номер

            for k in range( j+1, n):

                if (arr[i] + arr[j] + arr[k] < sum):

                    ans+=1

      

    return ans

  
# Драйверная программа

arr = [5, 1, 3, 4, 7]

n = len(arr)

sum = 12

print(countTriplets(arr, n, sum))

  
# Принесено Смитой

C #

// Простая программа на C # для подсчета триплетов с меньшей суммой
// чем данное значение

   

using System;

class Test

{

    static int[] arr = new int[]{5, 1, 3, 4, 7};

       

    static int countTriplets(int n, int sum)

    {

        // Инициализировать результат

        int ans = 0;

        

        // Зафиксируем первый элемент как A [i]

        for (int i = 0; i < n-2; i++)

        {

           // Исправить второй элемент как A [j]

           for (int j = i+1; j < n-1; j++)

           {

               // Теперь ищем третий номер

               for (int k = j+1; k < n; k++)

                   if (arr[i] + arr[j] + arr[k] < sum)

                       ans++;

           }

        }

        

        return ans;

    }

       

    // Метод драйвера для проверки вышеуказанной функции

    public static void Main() 

    {

        int sum = 12; 

        Console.Write(countTriplets(arr.Length, sum));

    }

}


Выход:

4

Временная сложность вышеуказанного решения составляет O (n 3 ). Эффективное решение может считать триплеты в O (n 2 ), сначала отсортировав массив, а затем используя метод 1 этого поста в цикле.

1) Sort the input array in increasing order.
2) Initialize result as 0.
3) Run a loop from i = 0 to n-2.  An iteration of this loop finds all
   triplets with arr[i] as first element.
     a) Initialize other two elements as corner elements of subarray
        arr[i+1..n-1], i.e., j = i+1 and k = n-1
     b) Move j and k toward each other until they meet, i.e., while (j = sum), then do k--

            // Else for current i and j, there can (k-j) possible third elements
            // that satisfy the constraint.
            (ii) Else Do ans += (k - j) followed by j++ 

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для подсчета триплетов с суммой, меньшей заданного значения
#include<bits/stdc++.h>

using namespace std;

  

int countTriplets(int arr[], int n, int sum)

{

    // Сортировка входного массива

    sort(arr, arr+n);

  

    // Инициализировать результат

    int ans = 0;

  

    // Каждая итерация цикла считает триплет

    // первый элемент как arr [i].

    for (int i = 0; i < n - 2; i++)

    {

        // Инициализируем два других элемента как угловые

        // подмассива обр [j + 1..k]

        int j = i + 1, k = n - 1;

  

        // Используем концепцию Meet in the Middle

        while (j < k)

        {

            // Если сумма текущего триплета больше или равна,

            // перемещаем правый угол, чтобы искать меньшие значения

            if (arr[i] + arr[j] + arr[k] >= sum)

                k--;

  

            // Остальное переместить в левый угол

            else

            {

                // Это важно. Для текущих я и J, там

                // может быть всего kj третьих элементов.

                ans += (k - j);

                j++;

            }

        }

    }

    return ans;

}

  
// Драйвер программы

int main()

{

    int arr[] = {5, 1, 3, 4, 7};

    int n = sizeof arr / sizeof arr[0];

    int sum = 12;

    cout << countTriplets(arr, n, sum) << endl;

    return 0;

}

Джава

// Простая Java-программа для подсчета триплетов с меньшей суммой
// чем данное значение

  

import java.util.Arrays;

  

class Test

{

    static int arr[] = new int[]{5, 1, 3, 4, 7};

      

    static int countTriplets(int n, int sum)

    {

        // Сортировка входного массива

        Arrays.sort(arr);

       

        // Инициализировать результат

        int ans = 0;

       

        // Каждая итерация цикла считает триплет

        // первый элемент как arr [i].

        for (int i = 0; i < n - 2; i++)

        {

            // Инициализируем два других элемента как угловые

            // подмассива обр [j + 1..k]

            int j = i + 1, k = n - 1;

       

            // Используем концепцию Meet in the Middle

            while (j < k)

            {

                // Если сумма текущего триплета больше или равна,

                // перемещаем правый угол, чтобы искать меньшие значения

                if (arr[i] + arr[j] + arr[k] >= sum)

                    k--;

       

                // Остальное переместить в левый угол

                else

                {

                    // Это важно. Для текущих я и J, там

                    // может быть всего kj третьих элементов.

                    ans += (k - j);

                    j++;

                }

            }

        }

        return ans;

    }

      

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        int sum = 12

        System.out.println(countTriplets(arr.length, sum));

    }

}

python3

# Python3 программа для подсчета тройки
# сумма меньше заданного значения

  

  
# Функция для подсчета триплетов с меньшей суммой
# чем заданное значение

def countTriplets(arr,n,sum):

      

    # Сортировать входной массив

    arr.sort()

      

    # Инициализировать результат

    ans = 0

      

    # Каждая итерация цикла считает триплет

    # первый элемент как arr [i].

    for i in range(0,n-2):

          

        # Инициализировать два других элемента как угловые

        № подмассива обр [j + 1..k]

        j = i + 1

        k = n-1

  

        # Используйте концепцию Meet in the Middle

        while(j < k):

              

            # Если сумма текущего триплета больше или равна,

            # переместить правый угол, чтобы найти меньшие значения

            if (arr[i]+arr[j]+arr[k] >=sum):

                k = k-1

              

            # Остальное переместить в левый угол

            else:

                  

                # Это важно. Для текущих я и J, там

                # может быть всего kj третьих элементов.

                ans += (k - j)

                j = j+1

      

    return ans

  
# Драйверная программа

if __name__=='__main__':

    arr = [5, 1, 3, 4, 7

    n = len(arr) 

    sum = 12

    print(countTriplets(arr, n, sum)) 

      
# Этот код предоставлен
# Ятин Гупта

C #

// Простая программа на C # для подсчета
// тройки с суммой меньше
// чем данное значение

using System;

  

class GFG

{

    static int []arr = new int[]{5, 1, 3, 4, 7};

      

    static int countTriplets(int n, int sum)

    {

        // Сортировка входного массива

        Array.Sort(arr);

      

        // Инициализировать результат

        int ans = 0;

      

        // Каждая итерация цикла

        // считает тройку

        // первый элемент как arr [i].

        for (int i = 0; i < n - 2; i++)

        {

            // Инициализируем два других

            // элементы как угловые элементы

            // подмассива обр [j + 1..k]

            int j = i + 1, k = n - 1;

      

            // Используем концепцию Meet in the Middle

            while (j < k)

            {

                // Если сумма текущего триплета

                // больше или равно, двигайтесь вправо

                // угол для поиска меньших значений

                if (arr[i] + arr[j] + arr[k] >= sum)

                    k--;

      

                // Остальное переместить в левый угол

                else

                {

                    // Это важно. За

                    // текущие i и j, там

                    // может быть всего kj третьих элементов.

                    ans += (k - j);

                    j++;

                }

            }

        }

        return ans;

    }

      

    // Код драйвера

    public static void Main() 

    {

        int sum = 12; 

        Console.Write(countTriplets(arr.Length, sum));

    }

}

  
// Этот код предоставлен Smitha


Выход:

4

Спасибо Gaurav Ahirwar за то, что он предложил это решение.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчет триплетов с суммой меньше заданного значения

0.00 (0%) 0 votes