Data Modelling & AI Data Structure & Algorithm

Sum of special triplets having elements from 3 arrays

23 June 2025

0

Given three arrays A, B, and C, the task is to find sum of values of all special triplets. A special triplet is defined as a triplet (X, Y, Z) where the condition :
X ? Y and Z ? Y always hold true. The value of each triplet (X, Y, Z) is given by:

f(X, Y, Z) = (X + Y) * (Y + Z)

Note: If a triplet is not ‘special’, f(x, y, z) = 0 for that particular triplet.

Examples:

Input : A = {1, 4, 5}, B = {2, 3}, C = {2, 1, 3}
Output : 81
Explanation
The special triplets and their values are given below
Triplet      f(x, y, z) = (x + y) * (y + z)
(1, 2, 2)         (1 + 2) * (2 + 2)  = 12
(1, 2, 1)         (1 + 2) * (2 + 1)  =  9
(1, 3, 2)         (1 + 3) * (3 + 2)  = 20
(1, 3, 1)         (1 + 3) * (3 + 1)  = 16
(1, 3, 3)         (1 + 3) * (3 + 3)  = 24
-------------------------------------
                           Sum = 81

Method 1 (Brute Force): We generate all triplets and check if a triplet is a special triplet, we calculate the value of the triplet using f(x, y, z) where (x, y, z) is a special triplet, and add it to the final sum of all such special triplets.

Implementation:

C++

// C++ Program to find sum of values of 
// all special triplets
#include <bits/stdc++.h>
using namespace std;
 
/* Finding special triplets (x, y, z) where
   x belongs to A; y belongs to B and z 
   belongs to C; p, q and r are size of 
   A, B and C respectively */
int findSplTripletsSum(int a[], int b[], int c[], 
                             int p, int q, int r)
{
 
    int sum = 0;
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < q; j++) {
            for (int k = 0; k < r; k++) {
 
                // (a[i], b[j], c[k]) is special if
                // a[i] <= b[j] and c[k] <= b[j];
                if (a[i] <= b[j] && c[k] <= b[j]) {
 
                    // calculate the value of this special
                    // triplet and add sum of all values 
                    // of such triplets
                    sum +=  (a[i] + b[j]) * (b[j] + c[k]);
                }
            }
        }
    }
    return sum;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 4, 5 };
    int B[] = { 2, 3 };
    int C[] = { 2, 1, 3 };
 
    int p = sizeof(A) / sizeof(A[0]);
    int q = sizeof(B) / sizeof(B[0]);
    int r = sizeof(C) / sizeof(C[0]);
 
    cout << "Sum of values of all special triplets = "
         << findSplTripletsSum(A, B, C, p, q, r) << endl;
}

Java

// Java Program to find sum of values of 
// all special triplets
class GFG
{
 
/* Finding special triplets (x, y, z) where
x belongs to A; y belongs to B and z 
belongs to C; p, q and r are size of 
A, B and C respectively */
static int findSplTripletsSum(int a[], int b[], int c[], 
                            int p, int q, int r)
{
 
    int sum = 0;
    for (int i = 0; i < p; i++) 
    {
        for (int j = 0; j < q; j++)
        {
            for (int k = 0; k < r; k++) 
            {
 
                // (a[i], b[j], c[k]) is special if
                // a[i] <= b[j] and c[k] <= b[j];
                if (a[i] <= b[j] && c[k] <= b[j])
                {
 
                    // calculate the value of this special
                    // triplet and add sum of all values 
                    // of such triplets
                    sum += (a[i] + b[j]) * (b[j] + c[k]);
                }
            }
        }
    }
    return sum;
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 1, 4, 5 };
    int B[] = { 2, 3 };
    int C[] = { 2, 1, 3 };
 
    int p = A.length;
    int q = B.length;
    int r = C.length;
 
    System.out.print("Sum of values of all special triplets = "
                    + findSplTripletsSum(A, B, C, p, q, r) +"\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 Program to find sum of values of 
# all special triplets
 
# Finding special triplets (x, y, z) where
# x belongs to A y belongs to B and z 
# belongs to C p, q and r are size of 
# A, B and C respectively
def findSplTripletsSum(a, b, c, p, q, r):
    summ = 0
    for i in range(p):
        for j in range(q):
            for k in range(r):
 
                # (a[i], b[j], c[k]) is special if
                # a[i] <= b[j] and c[k] <= b[j]
                if (a[i] <= b[j] and c[k] <= b[j]):
 
                    # calculate the value of this special
                    # triplet and add sum of all values 
                    # of such triplets
                    summ += (a[i] + b[j]) * (b[j] + c[k])
    return summ
 
# Driver Code
A = [1, 4, 5 ]
B = [2, 3 ]
C = [2, 1, 3 ]
 
p = len(A)
q = len(B)
r = len(C)
 
print("Sum of values of all special triplets = ",
            findSplTripletsSum(A, B, C, p, q, r))
 
# This code is contributed by Mohit kumar 29

C#

// C# Program to find sum of values of 
// all special triplets
using System;
 
class GFG
{
 
/* Finding special triplets (x, y, z) where
x belongs to A; y belongs to B and z 
belongs to C; p, q and r are size of 
A, B and C respectively */
static int findSplTripletsSum(int []a, int []b, int []c, 
                            int p, int q, int r)
{
 
    int sum = 0;
    for (int i = 0; i < p; i++) 
    {
        for (int j = 0; j < q; j++)
        {
            for (int k = 0; k < r; k++) 
            {
 
                // (a[i], b[j], c[k]) is special if
                // a[i] <= b[j] and c[k] <= b[j];
                if (a[i] <= b[j] && c[k] <= b[j])
                {
 
                    // calculate the value of this special
                    // triplet and add sum of all values 
                    // of such triplets
                    sum += (a[i] + b[j]) * (b[j] + c[k]);
                }
            }
        }
    }
    return sum;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 1, 4, 5 };
    int []B = { 2, 3 };
    int []C = { 2, 1, 3 };
 
    int p = A.Length;
    int q = B.Length;
    int r = C.Length;
 
    Console.Write("Sum of values of all special triplets = "
                    + findSplTripletsSum(A, B, C, p, q, r) +"\n");
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// javascript Program to find sum of values of 
// all special triplets    
     /* Finding special triplets (x, y, z) where x belongs to A; 
        y belongs to B and z  belongs to C; p, q and r are size 
        of A, B and C respectively */
    function findSplTripletsSum(a , b , c , p , q , r) {
 
        var sum = 0;
        for (i = 0; i < p; i++) {
            for (j = 0; j < q; j++) {
                for (k = 0; k < r; k++) {
 
                    // (a[i], b[j], c[k]) is special if
                    // a[i] <= b[j] and c[k] <= b[j];
                    if (a[i] <= b[j] && c[k] <= b[j]) {
 
                        // calculate the value of this special
                        // triplet and add sum of all values
                        // of such triplets
                        sum += (a[i] + b[j]) * (b[j] + c[k]);
                    }
                }
            }
        }
        return sum;
    }
 
    // Driver Code
     
        var A = [ 1, 4, 5 ];
        var B = [ 2, 3 ];
        var C = [ 2, 1, 3 ];
 
        var p = A.length;
        var q = B.length;
        var r = C.length;
 
        document.write("Sum of values of all special triplets = "
        + findSplTripletsSum(A, B, C, p, q, r) + "\n");
 
// This code is contributed by todaysgaurav 
</script>

Output

Sum of values of all special triplets = 81

The Time Complexity of this approach is O(P * Q * R) where P, Q, and R are the sizes of the three arrays A, B, and C respectively.

Method 2 (Efficient):

Suppose,
Array A contains elements {a, b, c, d, e},
Array B contains elements {f, g, h, i} and
Array C contains elements {j, k, l, m}.

First, we sort the arrays A and C so that we are able to find the number of elements in arrays A and C that are less than a particular B_i which can be done by applying binary search on each value of B_i.

Let’s suppose that at particular index i, the element of array B is B_i. Let’s also suppose that after we are done sorting A and C, we have elements {a, b, c} belonging to array A which are less than or equal to B_i and elements {j, k} belonging to array C which is also less than B_i.

Lets take B_i = Y from here on.

Let, Total Sum of values of all special triplets = S 
We Know S = ? f(x, y, z) for all possible (x, y, z)

Since elements {a, b, c} of Array A and elements {j, k} of array C are less than Y,
the Special Triplets formed consists of triplets formed only using these elements 
with Y always being the second element of every possible triplet

All the Special Triplets and their corresponding values are shown below:

Triplet   f(x, y, z) = (x + y) * (y + z)
(a, Y, j)         (a + Y)(Y + j)  
(a, Y, k)         (a + Y)(Y + k)  
(b, Y, j)         (b + Y)(Y + j)  
(b, Y, k)         (b + Y)(Y + k)  
(c, Y, j)         (c + Y)(Y + j)  
(c, Y, k)         (c + Y)(Y + k)

The sum of these triplets is
S = (a + Y)(Y + j) + (a + Y)(Y + k) + (b + Y)(Y + j) + (b + Y)(Y + k) 
    + (c + Y)(Y + j) + (c + Y)(Y + k)

Taking (a + X), (b + X) and (c + x) as common terms we have,

S = (a + Y)(Y + j + Y + k) + (b + Y)(Y + j + Y + k) + (c + Y)(Y + j + Y + k)
Taking (2Y + j + k) common from every term,
S = (a + Y + b + Y + c + Y)(2Y + j + k)  

? S = (3Y + a + b + c)(2Y + j + k)

Thus,
S = (N * Y + S1) * (M * Y + S2) 
where, 
N = Number of elements in A less than Y,
M = Number of elements in C less than Y,
S1 = Sum of elements in A less than Y and
S2 = Sum of elements in C less than Y

So for every element in B, we can find the number of elements less than it in arrays A and C using Binary Search and the sum of these elements can be found using prefix sums

Implementation:

C++

// C++ Program to find sum of values
// of all special triplets
#include <bits/stdc++.h>
using namespace std;
 
/* Utility function for findSplTripletsSum() 
finds total sum of values of all special 
triplets */
int findSplTripletsSumUtil(int A[], int B[], int C[],
                   int prefixSumA[], int prefixSumC[], 
                                 int p, int q, int r)
{
 
    int totalSum = 0;
 
    // Traverse through whole array B
    for (int i = 0; i < q; i++) {
 
        // store current element Bi
        int currentElement = B[i];
 
        // n = number of elements in A less than current
        // element
        int n = upper_bound(A, A + p, currentElement) - A;
 
        // m = number of elements in C less than current 
        // element
        int m = upper_bound(C, C + r, currentElement) - C;
 
        // if there are Elements neither in A nor C which 
        // are less than or equal to the current element
        if (n == 0 || m == 0)
            continue;
 
        /* total sum = (n * currentElement + sum of first
           n elements in A) + (m * currentElement + sum of 
           first m elements in C) */
        totalSum += 
            ((prefixSumA[n - 1] + (n * currentElement)) *
              (prefixSumC[m - 1] + (m * currentElement)));
    }
 
    return totalSum;
}
 
/* Builds prefix sum array for arr of size n
and returns a pointer to it */
int* buildPrefixSum(int* arr, int n)
{
 
    // Dynamically allocate memory tp Prefix Sum Array
    int* prefixSumArr = new int[n];   
 
    // building the prefix sum
    prefixSumArr[0] = arr[0];
    for (int i = 1; i < n; i++) 
        prefixSumArr[i] = prefixSumArr[i - 1] + arr[i];    
 
    return prefixSumArr;
}
 
/* Wrapper for Finding special triplets (x, y, z) 
   where x belongs to A; y belongs to B and z 
   belongs to C; p, q and r are size of 
   A, B and C respectively */
int findSplTripletsSum(int A[], int B[], int C[],
                             int p, int q, int r)
{
 
    int specialTripletSum = 0;
 
    // sort arrays A and C
    sort(A, A + p);
    sort(C, C + r);
 
    // build prefix arrays for A and C
    int* prefixSumA = buildPrefixSum(A, p);
    int* prefixSumC = buildPrefixSum(C, r);
 
    return findSplTripletsSumUtil(A, B, C, 
           prefixSumA, prefixSumC, p, q, r);
}
 
// Driver Code
int main()
{
    int A[] = { 1, 4, 5 };
    int B[] = { 2, 3 };
    int C[] = { 2, 1, 3 };
    int p = sizeof(A) / sizeof(A[0]);
    int q = sizeof(B) / sizeof(B[0]);
    int r = sizeof(C) / sizeof(C[0]);
 
    cout << "Sum of values of all special triplets = "
         << findSplTripletsSum(A, B, C, p, q, r);
}

Java

// Java Program to find sum of values of 
// all special triplets
import java.io.*;
import java.util.*;
 
public class GFG {
     
    /* Finding special triplets (x, y, z)
    where x belongs to A; y belongs to B
    and z belongs to C; p, q and r are 
    size of A, B and C respectively */
    static int findSplTripletsSum(int []a, 
                  int []b, int []c, int p,
                             int q, int r)
    {
        int sum = 0;
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < q; j++) {
                for (int k = 0; k < r; k++)
                {
     
                    // (a[i], b[j], c[k]) is
                    // special if a[i] <= b[j]
                    // and c[k] <= b[j];
                    if (a[i] <= b[j] && 
                                 c[k] <= b[j])
                    {
     
                        // calculate the value
                        // of this special
                        // triplet and add sum
                        // of all values 
                        // of such triplets
                        sum += (a[i] + b[j]) 
                               * (b[j] + c[k]);
                    }
                }
            }
        }
        return sum;
    }
     
    // Driver Code
    public static void main(String args[])
    {
        int []A = { 1, 4, 5 };
        int []B = { 2, 3 };
        int []C = { 2, 1, 3 };
     
        int p = A.length;
        int q = B.length;
        int r = C.length;
     
        System.out.print("Sum of values of all"
                       + " special triplets = "
        + findSplTripletsSum(A, B, C, p, q, r));
    }
}
 
// This code is contributed by Manish Shaw
// (manishshaw1)

Python3

# Python3 Program to find sum of values of  
# all special triplets 
 
# Finding special triplets (x, y, z) 
# where x belongs to A; y belongs to B 
# and z belongs to C; p, q and r are  
# size of A, B and C respectively 
def findSplTripletsSum(a, b, c, p, q, r):
    sum = 0
    for i in range(p):
        for j in range(q):
            for k in range(r):
               
                # (a[i], b[j], c[k]) is 
                # special if a[i] <= b[j] 
                # and c[k] <= b[j];
                if(a[i] <= b[j] and c[k] <= b[j]):
                   
                    # calculate the value 
                    # of this special 
                    # triplet and add sum 
                    # of all values  
                    # of such triplets 
                    sum += (a[i] + b[j]) * (b[j] + c[k])
    return sum
 
# Driver Code 
A = [1, 4, 5]
B = [2, 3 ]
C = [2, 1, 3]
p = len(A)
q = len(B)
r = len(C)
 
print("Sum of values of all","special triplets =",findSplTripletsSum(A, B, C, p, q, r))
 
# This code is contributed by avanitrachhadiya2155

C#

// C# Program to find sum of values of 
// all special triplets
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
     
    /* Finding special triplets (x, y, z) where
       x belongs to A; y belongs to B and z 
       belongs to C; p, q and r are size of 
       A, B and C respectively */
    static int findSplTripletsSum(int []a, int []b, int []c, 
                                       int p, int q, int r)
    {
        int sum = 0;
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < q; j++) {
                for (int k = 0; k < r; k++) {
     
                    // (a[i], b[j], c[k]) is special if
                    // a[i] <= b[j] and c[k] <= b[j];
                    if (a[i] <= b[j] && c[k] <= b[j]) {
     
                        // calculate the value of this special
                        // triplet and add sum of all values 
                        // of such triplets
                        sum += (a[i] + b[j]) * (b[j] + c[k]);
                    }
                }
            }
        }
        return sum;
    }
     
    // Driver Code
    public static void Main()
    {
        int []A = { 1, 4, 5 };
        int []B = { 2, 3 };
        int []C = { 2, 1, 3 };
     
        int p = A.Length;
        int q = B.Length;
        int r = C.Length;
     
        Console.WriteLine("Sum of values of all special triplets = "
                            + findSplTripletsSum(A, B, C, p, q, r));
    }
}
 
// This code is contributed by 
// Manish Shaw (manishshaw1)

Javascript

<script>
// Javascript Program to find sum of values of 
// all special triplets
     
     /* Finding special triplets (x, y, z)
    where x belongs to A; y belongs to B
    and z belongs to C; p, q and r are 
    size of A, B and C respectively */
    function findSplTripletsSum(a,b,c,p,q,r)
    {
        let sum = 0;
        for (let i = 0; i < p; i++) {
            for (let j = 0; j < q; j++) {
                for (let k = 0; k < r; k++)
                {
       
                    // (a[i], b[j], c[k]) is
                    // special if a[i] <= b[j]
                    // and c[k] <= b[j];
                    if (a[i] <= b[j] && 
                                 c[k] <= b[j])
                    {
       
                        // calculate the value
                        // of this special
                        // triplet and add sum
                        // of all values 
                        // of such triplets
                        sum += (a[i] + b[j]) 
                               * (b[j] + c[k]);
                    }
                }
            }
        }
        return sum;
    }
     
    // Driver Code
    let A=[1, 4, 5];
    let B=[ 2, 3 ];
    let C=[2, 1, 3 ];
     
    let p = A.length;
    let q = B.length;
    let r = C.length;
     
    document.write("Sum of values of all"
                       + " special triplets = "
        + findSplTripletsSum(A, B, C, p, q, r));
 
// This code is contributed by patel2127
</script>

Output

Sum of values of all special triplets = 81

Since we need to iterate through the entire array B and for every element apply binary searches in array A and C, the Time Complexity of this approach is O(Q * (logP + logR)) where P, Q, and R are the sizes of the three arrays A, B, and C respectively.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Sum of special triplets having elements from 3 arrays

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

Beyond Context Overload: How Parlant × Milvus Brings Control and Clarity to LLM Agent Behavior

Understanding IVF Vector Index: How It Works and When to Choose It Over HNSW

LEAVE A REPLY Cancel reply

Most Popular

Why your favorite creator uses one of these. [Video]

I stopped wasting money on unnecessary repair visits — here’s how NotebookLM ended my home maintenance chaos

6 things I am doing to reduce my digital footprint

My laptop broke, payday was far away, and an Android app quietly saved the day

EDITOR PICKS

Why your favorite creator uses one of these. [Video]

I stopped wasting money on unnecessary repair visits — here’s how NotebookLM ended my home maintenance chaos

6 things I am doing to reduce my digital footprint

POPULAR POSTS

Why your favorite creator uses one of these. [Video]

I stopped wasting money on unnecessary repair visits — here’s how NotebookLM ended my home maintenance chaos

6 things I am doing to reduce my digital footprint

POPULAR CATEGORY

ABOUT US

FOLLOW US