Beautiful Triplets

Beautiful Triplets

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.

For example, the sequence arr = [2,2,3,4,5] and 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. It must return an integer that represents the number of beautiful triplets in the sequence.

beautifulTriplets has the following parameters:

  • d: an integer
  • arr: an array of integers, sorted ascending

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]

Output Format

Print a single line denoting the number of beautiful triplets in the sequence.

Sample Input

1
2
7 3
1 2 4 5 7 8 10

Sample Output

1
3

Explanation

The input sequence is 1,2,4,5,7,8,10, and our beautiful difference d = 3. 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Complete the beautifulTriplets function below.
function beautifulTriplets(d, arr) {
let count = arr[0];
let max = arr[arr.length - 1];
let result = 0;

let { values } = new Array(arr.length).fill(0).reduce(
(target, item, index) => {
target["values"][arr[index]] = target["values"][arr[index]]
? (target["values"][arr[index]] += 1)
: 1;

return target;
},
{ values: {} }
);

while (count <= max) {
values[count] &&
values[count + d] &&
values[count + d * 2] &&
(result += Math.max(
values[count],
values[count + d],
values[count + d * 2]
));

count++;
}

return result;
}
Buy Me A Coffee

Comments

10Days of JS 30Days of Code Algorithm Android Debug Bridge Android Debugging Basic for Web Blog Browsers Chrome으로 Android Debugging 방법 Correctness and the Loop Invariant hackerrank solution in javascript Debug Tools Development Environment in MacOS ES6 Front-End Funny String of Algorithms hackerrank solution in javascript Funny String of Algorithms hackerrank solution in typescript Generator Github Page with Hexo Github Pages HackerRank HackerRank in a String of Algorithms hackerrank solution in javascript HackerRank in a String of Algorithms hackerrank solution in typescript Hexo Hexo Icarus theme Hexo 블로그 만들기 Hexo+Github How Browsers work Insertion Sort - Part 1 hackerrank solution in javascript Insertion Sort - Part 2 hackerrank solution in javascript JS Library JavaScript Level1 Level2 Loops MacOS 개발 환경 설정하기 Mobile web Debugging Node.js Pangrams of Algorithms hackerrank solution in javascript Pangrams of Algorithms hackerrank solution in typescript Problem Solving Programmers Quicksort 1 - Partition hackerrank solution in javascript React RoadMap Running Time of Algorithms hackerrank solution in javascript Safari Debugging Safari Technology Preview Settings Sorting String Strings Strong Password of Algorithms hackerrank solution in javascript TypeScript blog iPhone Safari Debugging 방법 insertion sort 모바일 웹 디버깅 아이폰 사파리를 디버깅하는 방법 안드로이드 디버그 브리지 안드로이드 디버깅하는 방법
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×