0 like 0 dislike
473 views
Expected Time Complexity : O(N*N) , where 'N'  is the size of array .

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 400 10000 5 5 300

(x,y,z) = (100,200,300)

Output : There is only 1 triplet  (100,200,300) in the array , hence answer is '1' .

Note :

1)Algorithm-explanation is must .

3)Use Format option while adding code

The triplet is valid only if x occurs before y, and y occurs before z .
| 473 views

1 like 0 dislike
```I think i get it wrong, coz O(n) solution exists. Jump to last for debugged ouput and someone first tell
me wether or not this was the logic that question was expecting. Then i will edit and make algo clear +
remove unnecessary code.
Just Let me know

#include<bits/stdc++.h>

using namespace std;

void naiveSolution(vector<int> &a, vector<int> &b)    // TIME COMPLEXITY O(n3)

{

int n = a.size(),        ct = 0;

cout<<"Indexex are as follows "<<endl;

for(int i=0 ; i<n; i++)

{

int smallCt = 0;

if(a[i] == b)

for(int j=i+1 ; j<n ; j++)

{

if(a[j] == b)

for(int k=j+1 ; k<n ; k++)

{

if(a[k] == b)

printf("%d %d %d\n" , i , j , k),

ct++;

}

}

}

cout<<"Total count is using Naive with time complexity O(n3) is \t\t="<<ct<<endl;

}

void testSolution(vector<int> &a, vector<int> &b)     // timeComplxity O(n);

{

int n = a.size();

int ct1 = 0 , ct2 = 0 , ct3 = 0;

for(auto i : a)

{

if(i == b)

ct1++;

else if(i == b)

ct2 += ct1;

else if(i == b)

ct3 += ct2;

}

cout<<"Total count is using Optimised approach is with complexity O(n) is\t="<<ct3<<endl;

}

int32_t main()

{

vector<int> TC1 = {1,2,1,3,2,3,2,3};

vector<int> TC2 = {1,2,3,3,3,3};

vector<int> TC3 = {3,2,3,1,2,3,2,1,3,2,3,1,3};

vector<int> TC4 = {3,3,3,3,3};

vector<int> b = {1,2,3};

vector<int> TC = TC1;

naiveSolution(TC,b);

testSolution(TC,b);

}

Sample TEST CASE , idk whether or not I understand this question correctly, Coz O(n) solution can easily
be deduced. Let me know about whether or not this was the required Logic/Answer. Then I will add algo for
the same.

Smaple Input 1

[1,2,1,3,2,3,2,3]

(1,2,3)

Output For 1st Test Case : Debugged output

Indexex are as follows
0 1 3
0 1 5
0 1 7
0 4 5
0 4 7
0 6 7
2 4 5
2 4 7
2 6 7
Total count is using Naive with time complexity O(n3) is                = 9
Total count is using Optimised approach is with complexity O(n) is      = 9```
by Expert (1,790 points)
selected