Подсчитать подпоследовательность длины 4, в которой произведение первых трех элементов равно четвертому элементу

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

Примеры:

Input: arr[] = {10, 2, 2, 7, 40, 160}
Output: 2
Explanation:
Following are the subsequences of length 4 satisfying the given criteria:

1. {10, 2, 2, 40}, the product of the first three elements is 10*2*2 = 40(= fourth element).
2. {2, 2, 40, 160}, the product of the first three elements is 2*2*40 = 160(= fourth element).

Therefore, the total count of subsequence is 2.

Input: arr[] = {1, 1, 1, 1}
Output: 1

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы сгенерировать все возможные подпоследовательности и подсчитать те подпоследовательности, которые удовлетворяют заданным критериям. После проверки всех подпоследовательностей выведите полученное общее количество.
Временная сложность: O(2 ^N )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, найдя все подпоследовательности длины 3 и сохранив произведение трех в HashMap, а затем подсчитав подпоследовательность, зафиксировав каждый элемент как четвертый элемент и увеличив частоту произведения триплетов. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте переменную, скажем , как 0 , которая хранит количество результирующих подпоследовательностей.
• Инициализируйте неупорядоченную карту, скажем, M , которая хранит частоты произведения триплетов.
• Пройдите по заданному массиву, используя переменную i , и выполните следующие шаги:
  • Увеличьте значение ans на arr[i] , считая его четвертым элементом подпоследовательности.
  • Сгенерируйте все возможные пары массива в диапазоне [0, i – 1] и сохраните частоту произведения двух с arr[i] в карте M .
• После выполнения вышеуказанных шагов выведите значение ans как результирующее количество подпоследовательностей.

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

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