CODEWITHSUNDEEP
javaarraysalgorithm
Koustav Chatterjee
Koustav Chatterjee

Reputation: 67

Count and print Triplets in a sorted array

Given a sorted array of n integers, display triplets such that a[i] < a[j] < a[k]. My code is 

public static void countTriplets(int arr[], int index, int arr1[], int position)
{
    if (position == 3)
    {
        System.out.println(Arrays.toString(arr1));
        return;
    }
    for (int i = index; i < arr.length; i++)
    {
        arr1[position] = arr[i];
        countTriplets(arr, index + 1, arr1, position + 1);
    }
}

However it prints all possible triplets.Where am i going wrong ?

Upvotes: 0

Views: 2917

Answers (3)

Jim Mischel
Jim Mischel

Reputation: 134105

The simple way to do this is with nested loops:

for (int i = 0; i < arr.length-2; i++)
{
    for (int j = i+1; j < arr.length-1; j++)
    {
        for (int k = j+1; k < arr.length; k++)
        {
            // output the triplet arr[i], arr[j], arr[k]
            ++numTriplets;
        }
    }
}

The code above will do what you're asking. It does not take into account the possibility of duplicates in the source array. Given the array [1, 2, 3, 4, 5], it outputs:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

Update

The general solution to this problem is one of creating combinations. That is, selecting combinations of n items from a list of size m. The math tells us that the number of combinations is equal to:

   m!
---------
(n!)(m-n)!

Substituting numbers for your example, we have:

c = 5!/((3!) * (5-3)!)
  = 120/(6 * 2)
  = 120/12
  = 10

So you can compute the number of combinations in O(1) easily enough (if you use an approximation for the factorial function), but if you want to enumerate them your time complexity approaches O(m!) (for sufficiently large values of m).

You certainly can't enumerate all the combinations in O(n) or O(n log n). That would be kind of like asking for an algorithm that can enumerate all n-digit numbers in O(n) or O(n log n).

Upvotes: 1

user1952500
user1952500

Reputation: 6781

Count the number of unique elements in the array. Let it be 'N'. Then the answer is n * (n - 1) * (n - 2) / 6.

The reasoning is as follows: for any three distinct numbers a, b, c, we can form a tuple of sorted elements such that say b < c < a. Since we don't want repetitions, we have to count the number of unique elements.

For example, consider {1, 2, 3, 3, 4, 5, 5, 6} Number of unique elements = 6. The answer is (6 * 5 * 4) / 6 = 20.

Some code in C++:

#include <stdio.h>


int count_triplets(int *a, int n)
{
    int counter = 0;
    if (n < 3) {
        return 0;
    }

    for (int i = 0; i < n; i++) {
        // jump to the last of the repeated values
        if ((i < n - 1) && (a[i] == a[i + 1])) {
            continue;
        }
        for (int j = i + 1; j < n; j++) {
            // jump to the last of the repeated values
            if ((j < n - 1) && (a[j] == a[j + 1])) {
                continue;
            }
            for (int k = j + 1; k < n; k++) {
                // jump to the last of the repeated values
                if ((k < n - 1) && (a[k] == a[k + 1])) {
                    continue;
                }
                printf("[%d, %d, %d]\n", a[i], a[j], a[k]);
                counter ++;
            }
        }
    }

    return counter;
}

int main(int argc, char *argv[])
{
    printf("Enter the number of elements:");
    int n = 0;
    scanf("%d", &n);

    printf("Enter the elements:\n");
    int a[100] = {0};
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    int triplets = count_triplets(a, n);

    printf("Number of triplets = [%d]\n", triplets);

    return 0;
}

This is not the most efficient but should lead you to more efficient solutions.

Upvotes: 2

murali kurapati
murali kurapati

Reputation: 1586

the answer can be reduced to selection of three numbers from n numbers which is nc3 i.e return (n*(n-1)*(n-2))/3! where n>=3 else return 0

Upvotes: 0

Related Questions