Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Triple Sum

Sharing is caring!

Problem Statement
Given 3 arrays a, b, c of different sizes, find the number of distinct triplets (p, q, r) where p is an element of a, written as p \in a, q \in b, and r \in c, satisfying the criteria: p \le q and q \ge r

For example, given a=\left[3,5,7\right] b=\left[3,6\right] and c=\left[4,6,9\right] we find four distinct triplets: $latex(3,6,4), (3,6,6), (5,6,4), (5,6,6)$

Function Description
Complete the triplets function in the editor below. It must return the number of distinct triplets that can be formed from the given arrays.

triplets has the following parameter(s):
a, b, c: three arrays of integers.

Input Format
The first line contains 3 integers len_a, len_b, len_c, the sizes of the three arrays.
The next 3 lines contain space-separated integers numbering len_a, len_b, len_c respectively.

Constraints
1 \le len_a, len_b, len_c \le 10^5
1 \le all\ elements\ in\ a,b,c \le 10^8

Output Format
Print an integer representing the number of distinct triplets.

Sample Input 0

3 2 3
1 3 5
2 3
1 2 3

Sample Output 0

8

Explanation 0
The special triplets are (1,2,1), (1,2,2), (1,3,1), (1,3,2), (1,3,3), (3,3,1), (3,3,2), (3,3,3).

Solution

public class TripleSum {


    static int binarySearchIndexForValueLessEqual(int[] arr, int l, int h, int searchVal) {
        if (l < h) {
            int mid = (l + h) / 2;
            if (searchVal < arr[mid]) {
                return binarySearchIndexForValueLessEqual(arr, l, mid - 1, searchVal);
            }

            int result = binarySearchIndexForValueLessEqual(arr, mid + 1, h, searchVal);
            if (result == -1) {
                return mid;
            } else {
                return result;
            }

        } else {
            if (arr[l] <= searchVal) {
                return l;
            } else {
                return -1;
            }
        }
    }

    static long triplets(int[] a, int[] b, int[] c) {
        int[] arr = Arrays.stream(a).sorted().distinct().toArray();
        int[] brr = Arrays.stream(b).sorted().distinct().toArray();
        int[] crr = Arrays.stream(c).sorted().distinct().toArray();

        Map<Integer, Integer> smallerIndexA = new HashMap<>();
        Map<Integer, Integer> smallerIndexC = new HashMap<>();

        long count = 0;
        for (int i = 0; i < brr.length; i++) {
            int left = binarySearchIndexForValueLessEqual(arr, 0, arr.length - 1, brr[i]) + 1;
            smallerIndexA.put(brr[i], left);

            int right = binarySearchIndexForValueLessEqual(crr, 0, crr.length - 1, brr[i]) + 1;
            smallerIndexC.put(brr[i], right);

            count += ((long)left * (long)right);
        }
        
        return count;
    }


    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in4.txt"));
        Scanner scanner = new Scanner(System.in);

        String[] lenaLenbLenc = scanner.nextLine().split(" ");

        int lena = Integer.parseInt(lenaLenbLenc[0]);

        int lenb = Integer.parseInt(lenaLenbLenc[1]);

        int lenc = Integer.parseInt(lenaLenbLenc[2]);

        int[] arra = new int[lena];

        String[] arraItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < lena; i++) {
            int arraItem = Integer.parseInt(arraItems[i]);
            arra[i] = arraItem;
        }

        int[] arrb = new int[lenb];

        String[] arrbItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < lenb; i++) {
            int arrbItem = Integer.parseInt(arrbItems[i]);
            arrb[i] = arrbItem;
        }

        int[] arrc = new int[lenc];

        String[] arrcItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int i = 0; i < lenc; i++) {
            int arrcItem = Integer.parseInt(arrcItems[i]);
            arrc[i] = arrcItem;
        }

        long ans = triplets(arra, arrb, arrc);

        System.out.println(ans);

        scanner.close();
    }
}