Beautiful Triplets – HackerRank Solution

In this post, we will solve Beautiful Triplets HackerRank Solution. This problem (Beautiful Triplets) is a part of HackerRank Problem Solving series.

Problem

Given a sequence of integers a, a triplet (a[i], a[j], a[k]) is beautiful if:

• i < j < k
• a[j] – a[i] = a[k] – a[j] = d

Given an increasing sequenc of integers and the value of d, count the number of beautiful triplets in the sequence.

Example

arr = [2, 2, 3, 4, 5]
d = 1

There are three beautiful triplets, by index: [i, j, k] = [0, 2, 3], [1, 2, 3], [2, 3, 4]. To test the first triplet, arr[j] – arr[i] = 3 – 2 = 1 and arr[k] – arr[j] = 4 – 3 = 1.

Function Description

Complete the beautifulTriplets function in the editor below.

beautifulTriplets has the following parameters:

• int d: the value to match
• int arr[n]: the sequence, sorted ascending

Returns

• int: the number of beautiful triplets

Input Format

The first line contains 2 space-separated integers, n and d, the length of the sequence and the beautiful difference.
The second line contains n space-separated integers arr[i].

Constraints

• 1 <= n <= 10⁴
• 1 <= d <= 20
• 0 <= arr[i] <= 2 x 10⁴
• arr[i] > arr[i – 1]

Sample Input

STDIN           Function
-----           --------
7 3             arr[] size n = 7, d = 3
1 2 4 5 7 8 10  arr = [1, 2, 4, 5, 7, 8, 10]

Sample Output

3

Explanation

There are many possible triplets (arr[i], arr[j], arr[k]), but our only beautiful triplets are (1, 4, 7), (4, 7, 10) and (2, 5, 8) by value, not index. Please see the equations below:
7 – 4 = 4 – 1 = 3 = d
10 – 7 = 7 – 4 = 3 = d
8 – 5 = 5 – 2 = 3 = d

Recall that a beautiful triplet satisfies the following equivalence relation: arr[j] – arr[i] = arr[k] – arr[j] = d where i < j < k.

Solution – Beautiful Triplets – HackerRank Solution

C++

#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

int beautifulTriplets(int d, vector<int> arr) {
    int triplets=0;
    
    for(int i=0;i<arr.size();i++){
        for(int j=i+1;j<arr.size();j++){
            if (arr[j]-arr[i]==d) {
            for(int k=j+1;k<arr.size();k++){
                if(arr[k]-arr[j]==d){
                   triplets++;
                   break;
            }
            }
            }
        }
    }
return triplets;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int d = stoi(first_multiple_input[1]);

    string arr_temp_temp;
    getline(cin, arr_temp_temp);

    vector<string> arr_temp = split(rtrim(arr_temp_temp));

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        int arr_item = stoi(arr_temp[i]);

        arr[i] = arr_item;
    }

    int result = beautifulTriplets(d, arr);

    fout << result << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}

Python

import sys

def beautifulTriplets(d, arr):
    res = 0
    
    for el in arr:
        if el + d in arr and el + 2*d in arr:
            res += 1
            
    return res

    
if __name__ == "__main__":
    n, d = input().strip().split(' ')
    n, d = [int(n), int(d)]
    arr = list(map(int, input().strip().split(' ')))
    result = beautifulTriplets(d, arr)
    print(result)

Java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[] a = new int[n];
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            set.add(a[i]);
        }
        
        int ans = 0;
        
        for (int i = 0; i < n; i++) {
            if (set.contains(a[i]+d)&&set.contains(a[i]+2*d))
                ans++;
        }
        
        System.out.println(ans);
    }
}

Note: This problem (Beautiful Triplets) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.