Hello Programmers, In this post, you will know how to solve the HackerRank Beautiful Triplets Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Beautiful Triplets Solution
Task
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 <= 104
- 1 <= d <= 20
- 0 <= arr[i] <= 2 x 104
- 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.
HackerRank Beautiful Triplets Solution
Beautiful Triplets Solution in C
#include<stdio.h>
int main(void){
int n,d;
scanf("%d %d",&n,&d);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
int s=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(a[j]-a[i]!=d) continue;
for(int k=j+1;k<n;k++){
if(a[j]-a[i]==a[k]-a[j] && a[k]-a[j]==d)s++;
}
}
}
printf("%d",s);
return 0;
}Beautiful Triplets Solution in Cpp
#include <iostream>
#include <cstring>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#define _USE_MATH_DEFINES
#include <math.h>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <assert.h>
using namespace std;
void smain();
int main(){
#ifdef TASK
freopen(TASK".in","rt",stdin);
const clock_t start = clock();
#endif
smain();
#ifdef TASK
cerr << "\nTotal Execution Time: " << float( clock () - start ) / CLOCKS_PER_SEC << endl;
#endif
return 0;
}
#ifndef M_PI
#define M_PI 3.14159265358979311599796346854418516
#endif
#define forn(i,n) for (int i=0;i<n;i++)
#define rforn(i,n) for (int i=n-1;i>=0;i--)
#define int long long
#define LL __int128
#define mp(a,b) make_pair(a,b)
#define INF 2305843009213693951LL
#define MOD 1000000007
#define EPS 1E-6
#define N 200001
/* --------- END TEMPLATE CODE --------- */
int n, d;
int a[N];
void smain() {
for (; cin >> n >> d; ) {
forn(i, n) cin >> a[i];
int res = 0;
map<int, int> l, r;
forn(i, n) r[a[i]] += 1;
forn(i, n) {
r[a[i]] -= 1;
res += l[a[i]-d] * r[a[i]+d];
l[a[i]] += 1;
}
cout << res << '\n';
}
}Beautiful Triplets Solution in 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);
}
}Beautiful Triplets Solution in Python
rr = raw_input
rrM = lambda: map(int, rr().split())
N,D = rrM()
A = rrM()
#beau if i<j<k , ak - aj = aj - ai = d
from collections import defaultdict as ddic
seenL = ddic(int)
seenR = ddic(int)
for i in xrange(N):
for j in xrange(i+1,N):
if A[j]-A[i] == D:
seenL[j] += 1
seenR[i] += 1
ans = 0
for i in xrange(N):
ans += seenL[i] * seenR[i]
print ansBeautiful Triplets Solution using JavaScript
function processData(input) {
var inp = input.split("\n");
var n = parseInt(inp[0].split(" ")[0]);
var d = parseInt(inp[0].split(" ")[1]);
var a = inp[1].split(" ");
a = a.map(Number);
var triplets = 0;
var visited = [];
for(var i=0;i<n;i++){
visited[i] = false;
}
for(var i=0;i<n;i++){
if(visited[i])
continue;
visited[i] = true;
var count = 1
var k = a[i];
for(var j=i+1;j<n;j++){
if(a[j]-k == d){
visited[j] = true;
count++;
k = a[j];
}else if(a[j]-k>d){
break;
}
}
if(count>2){
triplets += count-2;
}
count = 1;
}
console.log(triplets);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Beautiful Triplets Solution in Scala
import scala.io.StdIn
object Solution {
def main(args: Array[String]) {
val Array(n, d) = StdIn.readLine().split("\\s+").map(_.toInt)
val a = StdIn.readLine().split("\\s+").map(_.toInt)
val index = a.zipWithIndex.groupBy(_._1).mapValues(_.length)
var cnt = 0L
for (j <- 1 until n) {
val is = index.getOrElse(a(j) - d, 0)
val ks = index.getOrElse(a(j) + d, 0)
cnt += is * ks
}
println(cnt)
}
}Beautiful Triplets Solution in Pascal
var a,b:array[0..1000000] of longint; n,d,i,j,ans:longint; begin read(n,d); for i:=1 to n do begin read(a[i]); inc(b[a[i]]); end; for i:=1 to n do for j:=i+1 to n do if (a[j]-a[i]=d) and (b[a[j]+d]>0) then inc(ans); writeln(ans); end.
Disclaimer: This problem (Beautiful Triplets) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.