Beautiful Triplets Hackerrank problem solution

Beautiful Triplets Hackerrank

Beautiful Triplets Hackerrank

Triplet:-

The combination of three numbers(random), specifically can be anything but should be a set of three numbers.

See the question at hacker rank:-   https://www.hackerrank.com/challenges/beautiful-triplets

Erica wrote an increasing sequence of n numbers (a0,a1,….,an-1) in her notebook. She considers a triplet (ai,aj,ak) to be beautiful if:
i<j<k
a[i]-a[j]=a[k]-a[j]=d

Given the sequence and the value of d, can you help Erica count the number of beautiful triplets in the sequence?

Input Format

The first line contains 2 space-separated integers,n (the length of the sequence) and d (the beautiful difference), respectively.
The second line contains n space-separated integers describing Erica’s increasing sequence, a0,a1,….,an-1.
Beautiful Triplets Hackerrank

Output Format:- Print a single line denoting the number of beautiful triplets in the sequence.

Sample Input

7 3
1 2 4 5 7 8 10
Sample Output:- 3

Explanation

Our input sequence is 1 2 4 5 7 8 10, and our beautiful difference d=3. There are many possible triplets (ai,aj,ak), but our only beautiful triplets are (1,4,7), (4,7,10) and (2,5,8). Please see the equations below:
4-1=7-4=3=d
7-4=10-7=3=d
5-2=8-5=3=d

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

Solution

Beautiful Triplets Hackerrank

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n,d,total=0;
    cin>>n>>d;
    int a[n];
    for(int i=0;i<n;i++) {
        cin>>a[i];        
    }
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(a[j] - a[i] == d){
                for(int k = j+1; k < n; k++){
                    if(a[k] - a[j] == d){
                        total++;
                    }
                }
            }
        }
    }
    cout<<total;
    return 0;
}
n, d = map(int , raw_input().split(" "))
a = map(int , raw_input().split(" "))

flag = [0] * (2 * 10000 + d + 1)
for val in a:
    flag[val] = 1

ans = 0
for val in a:
    if flag[val + d] and flag[val + d + d]:  #all three numbers required to form a triplet exists
        ans = ans + 1
print ans
n, d = map(int , raw_input().split())
a = map(int , raw_input().split())


ans = 0
for i in range(n):
    found = 0
    for j in range(i + 1, min(i + d + d + 1, n)):
        if a[j] - a[i] == d:
            found=found+1
        if a[j] - a[i] == d + d:
            found = found + 1
    if found == 2:
        ans = ans + 1 
print ans
Statistics
Difficulty: Easy
Time Complexity:
Required Knowledge: loop
Publish Date: Apr 16 2016
Originally featured in World Codesprint April

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.