Подсчитайте суммы пар, которые являются факторами суммы массива

Дан массив arr[] , состоящий из N целых чисел, задача состоит в том, чтобы найти количество пар, где i ≤ j , таких, что сумма пар делит сумму элементов массива.

Примеры:

Input: arr[] = {1, 2, 3, 4, 5}
Output: 3
Explanation:
Below are the pairs that divides the sum of array( = 1 + 2 + 3 + 4 + 5 = 15):

1. (1, 2): Sum of pairs = 1 + 2 = 3, that divides sum(= 15).
2. (1, 4): Sum of pairs = 1 + 4 = 5, that divides sum(= 15).
3. (2, 3): Sum of pairs = 2 + 3 = 5, that divides sum(= 15).

Therefore, the count of pairs is 3.

Input: arr[] = {1, 5, 2}
Output: 0

Подход: Данную задачу можно решить, сгенерировав из заданного массива все возможные пары (arr[i], arr[j]) такие, что i ≤ j , и подсчитав все те пары, сумма элементов которых делит сумму массива. После проверки всех возможных пар выведите полученное общее количество.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N ² )
Вспомогательное пространство: O(1)