The general elections are coming and so rahul and modi have started the preparations.An astrologer predicted that whoever solves the given problem first will win the elections.

The problem is as follows: Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

As I want modi to win,so you have to solve this problem for modi before rahul does...Good Luck


In the first line ,you will be given t the number of test cases ,for each test case you will be given n, the size of the array.In the next line you will be given n space separated elements of the array.

Input constraints :t<=10000, n<=10000 (sum of n over all test cases won't exceed 10^8)


Output the number of such triplets and subsequently print each of the triplets in a separate line in lexicographic order.


-1 0 1 2 -1
0 0 0
-1 -1 2
-1 0 1
0 0 0

hide comments
trijeet: 2018-06-14 04:40:38

Slight correction - the triplets should be printed in sorted order, not lexicographically (as character sorting). Good problem

mehul_sri: 2018-06-09 18:39:53

Nice problem!! Well done bro @be1035016 ;)

Ishwar: 2018-05-31 10:30:08

is it required to not to print the multiple combination of same three numbers?

RE:yes all arrangements of a triplet are considered identical

Last edit: 2018-06-01 09:14:50
learnerinblack: 2018-05-24 13:26:33

Finally AC, Oh gosh, pheww!
Advice: Check for duplicates! Costed me 4 hrs and God knows how many WAs :)

nadstratosfer: 2018-05-24 07:15:53

Input is badly formatted, line-based reading crashes a Python solution. Psetter, please check if there are no linebreaks between numbers of the same array. Other than that, well designed problem in that rejecting sub-optimal solutions still allows PyPy to get AC.

Last edit: 2018-05-24 07:34:32
sikh_coder: 2018-05-23 21:16:10

Can't think of a better sol than O(n^2*logn)...

finally AC :)

Last edit: 2018-05-23 21:21:20
be1035016: 2018-05-23 19:42:05

@vipul just to avoid sub-optimal solutions

Vipul Srivastava: 2018-05-23 18:13:56

@author you have changed the problem by adding more than one test case, is there a reason behind it? My ACd solution gets AC after adding code to handle more than one test case.

Added by:new
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)