Проверьте, присутствует ли в данном массиве вся возможная сумма триплетов.

Опубликовано: 19 Сентября, 2022

Учитывая массив arr[] размера N , задача состоит в том, чтобы проверить, если для всех различных троек индексов i, j, k, [ 0 ≤ i < j < k ≤ N-1 ] сумма arr[i] + arr[ j] + arr[k] присутствует в массиве.

Примеры :

Input: arr[] = {-1, 0, 0, 1}
Output: True
Explanation: For index 0, 1, 2: arr[i]+arr[j]+arr[k] = -1 + 0 + 0 = -1
For index 0, 1, 3: arr[i]+arr[j]+arr[k] = -1 + 0 + 1 = 0
For index 0, 2, 3: arr[i]+arr[j]+arr[k] = -1 + 0 + 1 = 0
For index 1, 2, 3: arr[i]+arr[j]+arr[k] = 0 + 0 + 1 = 1
-1, 0, 1 all are elements of the array arr[], so, the condition holds true.

Input: arr[] = {0, 0, 0}
Output: True

Подход : Задачу можно решить, используя следующую математическую идею:

If there are more than or equal to 3 positive elements or more than or equal to 3 negative elements, then the condition arr[i]+arr[j]+arr[k] = an element of the array cannot be true. 

Otherwise, push all the element of the array in a linear data structure like vector and if there are more than one zero in the array then push only one 0 in the vector, the vector will contain atmost 5 elements i.e., 2 positives, 2 negatives and 1 zero. 

Now, push all elements into a set for checking the condition, and apply bruteforce because there are only 5 elements atmost in the array. For checking the condition of the question, check if  v[i]+v[j]+v[k] is present in the set or not for all the triplets from the vector.

Выполните шаги, указанные ниже, чтобы реализовать наблюдение:

  • Инициализируйте переменные (скажем, CP = 0 и CN = 0 ) для подсчета положительных и отрицательных результатов соответственно.
  • Запустите цикл и поместите все элементы массива в вектор.
  • Если CP > 2 или CN < 2 в любой момент времени, то данное условие не может быть выполнено. Так что верните ложь.
  • Вставьте только один 0, если в векторе есть хотя бы один 0.
  • Теперь примените три вложенных цикла и проверьте, выполняется условие или нет.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность : O(N)

  • Подсчет частоты занимает O(N) времени
  • Конечный вектор может иметь не более 5 элементов, поэтому 3 вложенных цикла займут не более O (1) времени.

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ