THRSUM - ZERO TRIPLET


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

Input

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

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

Example

Input:
2
5
-1 0 1 2 -1
3
0 0 0
Output:
2
-1 -1 2
-1 0 1
1
0 0 0

hide comments
David: 2020-08-07 00:17:42

Does "unique triples" mean the indexes or values.
For example, is the answer to:
4
0 0 0 0
One set of "0 0 0" (unique values), or 4 sets of "0 0 0" (unique indexes)?

2. Does the order in the triple matter? I guess that we print a1 a2 a3, where a1 <= a2 <= a3, but the order of the triple is not stated.

Last edit: 2020-08-07 00:40:47
smso: 2019-01-18 05:14:51

O(N^2) => TLE
divide data into positives, zeros and negatives and consider cases,
e.g. (-1,-1,2), (-3,1,2),(-7,0,7),(0,0,0) => accepted

Last edit: 2019-01-18 05:15:17
akjol2049: 2018-11-18 07:26:40

constraints for the elements of the array?

RE->64-bit

Last edit: 2019-01-06 08:37:36
DOT: 2018-07-30 18:28:41

@Sushovan, ah, right! Thank you. :)

Sushovan Sen: 2018-07-30 14:33:35

1s is the time limit to solve a single file. There may be multiple input files, your 2.75s is run time of all the files which need not be less than a second.

DOT: 2018-07-29 20:04:53

Can anyone clarify what the 1s in time limit mean? I thought the solution should produce output for all test-cases within the set 1s limit. But my solution ran for 2.75s, yet got accepted. How come?

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

@learnerinblack
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 :)


Added by:ac_baz
Date:2018-05-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:https://www.hackerrank.com/contests/cnc-02/challenges/the-simplest-counting-problem/editorial