Triples


Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type

Given an array of integers, \(a\), compute the number of unique ways to satisfy the equation \(a_i + a_j = a_k\), where \(i \neq j \neq k\) and \(a_i \leq a_j\). To be unique, each counted equation after being filled in must never have been counted before.

Input Specification

The first line will contain a single integer \(N\), \(3 \leq N \leq 5000\).

The next line will contain \(N\) space separated integers, describing the array. \(1 \leq a_i \leq 10^6\)

Output Specification

The output will contain a single line, the number of unique triples that can be formed by the array.

Sample Input 1

4
1 5 3 2

Sample Output 1

2

Explanation for Sample 1

The unique equations are \(1 + 2 = 3\) and \(2 + 3 = 5\)

Sample Input 2

5
1 1 1 2 3

Sample Output 2

2

Explanation for Sample 2

The unique equations are \(1 + 1 = 2\) and \(1 + 2 = 3\)


Comments


  • 0
    MstrPikachu  commented on Jan. 5, 2020, 5:29 p.m.

    For the second sample, why is \(N\) equal to 4 when there are 5 elements in the array?


    • 0
      _  commented on Jan. 6, 2020, 8:49 p.m.

      Fixed