-
Notifications
You must be signed in to change notification settings - Fork 1
/
count the triplets.cpp
137 lines (106 loc) Β· 2.76 KB
/
count the triplets.cpp
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*
///////////////////////////////////////////
//Question/Info
Count the triplets
Easy Accuracy: 42.82% Submissions: 28089 Points: 2
Given an array of distinct integers. The task is to count all the triplets such that sum of two elements equals the third element.
Example 1:
Input:
N = 4
arr[] = {1, 5, 3, 2}
Output: 2
Explanation: There are 2 triplets:
1 + 2 = 3 and 3 +2 = 5
Γ’β¬βΉExample 2:
Input:
N = 3
arr[] = {2, 3, 4}
Output: 0
Explanation: No such triplet exits
Your Task:
You don't need to read input or print anything. Your task is to complete the function countTriplet() which takes the array arr[] and N as inputs and returns the triplet count
Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(1)
Constraints:
1 β€ N β€ 103
1 β€ arr[i] β€ 105
Company Tags
Amazon Arcesium
author: srj_v
///////////////////////////////////////////
*/
#include <bits/stdc++.h>
using namespace std;
// #define int long long int
#define sbit(x) __builtin_popcount(x)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define eb(x) emplace_back(x)
#define ct(x) cout << x << "\n";
#define ct2(x,y) cout << x << " " << y << "\n";
#define tc(x) cout << x << " ";
#define tc2(x,y) cout << x << " " << y << " ";
#define forn(i,n) for(int i = 0; i < (int)(n); ++i)
#define forx(i,x,n) for(int i = x; i < (int)(n); ++i)
#define nfor(i,n) for(int i = n-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define fsp(x,y) fixed << setprecision(y) << x
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007 // (1e9+7)
#define pii pair<int,int>
#define pis pair<int,string>
#define vi vector<int>
#define vii vector<pii>
#define mii map<int,int>
#define p_q priority_queue // priority_queue<int> (&) priority_queue< int,vi,greater<int> >
#define _IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long double ld;
typedef long long int lli;
#pragma GCC optimize("Ofast")
void c_p_c()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int32_t main() {
///////////
c_p_c();
///////////
_IOS
//////////
// code
/*
int t ; cin >> t; while(t--){}
*/
class Solution {
public:
int countTriplet(int arr[], int n)
{
// Your code goes here
sort(arr, arr + n);
int count = 0;
for (int i = n - 1 ; i >= 2 ; --i) {
// note that i is running till i==2....
int j = 0 ;
int k = i - 1;
while (j < k) {
if (arr[j] + arr[k] == arr[i]) {
++count;
++j; --k;
}
else if (arr[j] + arr[k] > arr[i]) {
--k;
}
else {
++j;
}
}
}
return count;
}
};
// cerr << "time: " << clock() << " ms" << '\n';
return 0;
}