Google | Phone Screen | Number of Quadruples in an unsorted array
Anonymous User
816

Find number of quadruples (x, y, z, w) in an unsorted array such that x + y + z = w and index(x) < index(y) < index(z) < index(w).

Example 1:

Input: [3, 5, 4, 7, 12, 1]
Output: 1
Explanation:
Beacuse (3, 5, 4, 12) is one quadruple such that 3 + 5 + 4 = 12 and index(3) < index (5) < index(4) < index(12).

Example 2:

Input: [3, 5, 4, 7, 12, 1, 10]
Output: 2
Exlanation:
(3, 5, 4, 12) is one quadruple such that 3 + 5 + 4 = 12 and index(3) < index (5) < index(4) < index(12).
(5, 4, 1, 10) is second quadruple such that 3 + 5 + 4 = 12 and index(5) < index (4) < index(1) < index(10).
Comments (4)