Menu Close

Count the number of beautiful triplets in the sequence…[Cprogm]FTC

Given a sequence of integers ‘a’, a triplet (a[i], a[j], a[k]) is beautiful if:
1)     i < j < k
2)    a[j] -a[i] = a[k]-a[j] = d
Given an increasing sequence of integers and the value of ‘d’, count the number of beautiful triplets in the sequence.

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

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

Explanation:
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

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.

#include <stdio.h>
#include<stdlib.h>
int main()
{
  int str[100];
  int n,d,s=0,i,j,k;
  scanf("%d %d",&n,&d);
  int *arr;
  arr=(int *)malloc(n*sizeof(int));
  *arr=n;
  for( i=0;i<n;i++)
  {scanf("%d",&str[i]);
  }
  for( i=0;i<n;i++){
      for( j=i+1;j<n;j++){
          if(str[j]-str[i]!=d) continue;
          for( k=j+1;k<n;k++){
              if(str[j]-str[i]==str[k]-str[j] && str[k]-str[j]==d)s++;
          }
      }
  }
  printf("%d",s);
return 0;
}

INPUT_1:
6  3
2  4  5  7  8  10

OUTPUT:
2


INPUT_2:
5  3
4  5  7  8  10

OUTPUT:
1


ILLUSTRATION

Executed using gcc terminal