Количество пар в массиве с произведением больше 0

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

Для заданного массива arr[] длины N задача состоит в том, чтобы подсчитать количество пар (i, j), таких что arr[i] * arr[j] > 0 и 0 ≤ i < j ≤ N . Также дано, что элемент массива может быть любым положительным целым числом, включая ноль, или может быть отрицательным целым числом.

Примеры:

Input: arr[] = {1, -5, 0, 2, -7} 
Output: 2
Explanation: Here product of (1, 2) and (-5, -7) is greater than 0.

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

Наивный подход: основной подход состоит в том, чтобы сгенерировать все возможные пары массива и подсчитать те пары, которые удовлетворяют заданному условию.

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

  • Используйте вложенный цикл для создания всех пар.
  • Проверьте, больше ли произведение пары 0, затем увеличьте количество .
  • Верните окончательный счет после создания всех пар.

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

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

Эффективный подход: проблема может быть решена на основе следующей идеи:

Multiplication of two numbers can be greater than zero only if both the numbers are negative or both the numbers are positive. And if one number is zero then it can not form pair with anyone in order to get the result as greater than zero. 

Чтобы реализовать идею, подсчитайте положительные числа и отрицательные числа. Затем получите количество пар, используя формулу комбинаторики n C 2 , то есть (положительное*(положительное-1)/2 + отрицательное*(отрицательное*-1)/2 ) . Для реализации идеи выполните следующие шаги:

  • Запустите цикл от i = 0 до N-1 :
    • Подсчитайте количество положительных и отрицательных чисел в массиве (скажем, представленное положительными и отрицательными числами).
  • Теперь вычислите общее количество пар из-за появления положительных и общее количество пар из-за появления отрицательных, используя приведенное выше наблюдение.
  • Возвращает общее количество вхождений.

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

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

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