Program to Find Number of Arithmetic Triplets.

Given a zero-based strictly increasing integer array arr[], and a positive integer diff. Write a program to return the number of unique arithmetic triplets.

Condition for Arithmetic Triplets:
Index i < j < k.
arr[j] - arr[i] == diff and,
arr[k] - arr[j] == diff (alert-passed)

Example:
Input: arr[] = {1, 3, 5, 6, 8, 11, 15}, diff = 2
Output: 1
Explanation:
(0, 1, 2) is an arithmetic triplet because 3 - 1 = 2 and 5 - 3 = 2

Input: arr[] = {0, 1, 4, 6, 7, 10}, diff = 3
Output: 2
Explanation:
(1, 2, 4) is an arithmetic triplet because both 7 - 4 = 3 and 4 - 1 = 3.
(2, 4, 5) is an arithmetic triplet because both 10 - 7 = 3 and 7 - 4 = 3.

There are multiple ways to solve this problem and here we will discuss brute-force and optimized solutions so you can get a better understanding of how to approach similar problems.

Approach 1: Brute Force Approach.

As the given array contains only positive numbers and elements are in sorted order, we can easily solve this problem by using three nested loops and defining the arithmetic triplet condition inside the inner loop.

Below is the C++ Implementation:

//C++ program to find arithmetic triplets
#include<iostream>
using namespace std;

//function definition
int arithmeticTriplet(int arr[], int size, int diff){
    //variable to get the count
    int count = 0;

    for(int i = 0; i < size; i++){
        for(int j = i + 1; j < size; j++){
            for(int k = j + 1; k < size; k++){
                if((arr[j] - arr[i]) == diff && (arr[k] - arr[j]) == diff){
                    count++;
                }
            }
        }
    }
    return count;
}

int main(){
    int arr[] = {0, 1, 4, 6, 7, 10};
    int size = sizeof(arr)/sizeof(arr[0]);

    int diff = 3;

    cout<<arithmeticTriplet(arr, size, diff);

    return 0;
}

Output:

Time Complexity: O(n^3)
Space Complexity: O(1)

The time complexity of the solution using the above approach is very high which is a good solution for big-size data. We have to think of a better and more optimized solution which we are going to discuss in our next approach.

Approach 2: Using a Hashmap.

Using a hashmap to store unique elements will help us reduce our time complexity.

Steps to follow:

Declare an unordered_map to keep track of unique elements of the array that we have seen so far and also initialize a count variable to count the number of arithmetic triplets.
Iterate over the given array, for each element arr[i] check if arr[i] - diff and arr[i] - 2*diff are present in our unordered_map, if yes then increase the value of count by 1.
Insert the correct element arr[i] into the unordered_map so we can use this value to find out more arithmetic triplets.
Return the count after processing all the elements of the given array.

Below is C++ Implementation:

//C++ code for finding arithmetic triplets
#include <iostream>
#include <unordered_set>
using namespace std;

//function declaration
int countTriplets(int arr[], int n, int diff) {
    unordered_set<int> seen;
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (seen.count(arr[i] - diff) && seen.count(arr[i] - 2 * diff)) {
            count++;
        }
        seen.insert(arr[i]);
    }

    return count;
}

int main() {

    int arr[] = {1, 3, 5, 6, 8, 11, 15};
    //size of array
    int n = sizeof(arr)/sizeof(arr[0]);

    int diff = 2;
    int count = countTriplets(arr, n, diff);
    cout << count << endl;

    return 0;
}

Output:

Time Complexity: O(n) where n is the length of the input array and we only need to loop over the array once.
Space Complexity: O(n) as we have used unordered_set to keep track of unique elements of the array.

Program to Find Number of Arithmetic Triplets.

No comments:

Post a Comment