Наименьший индекс, который разбивает массив на два подмассива с одинаковым произведением

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

Примеры:

Input: arr[] = {1, 2, 3, 3, 2, 1}
Output: 3
Explanation: Index 3 generates subarray {arr[1], arr[3]} with product 6 (= 1 * 2 * 3) and {arr[4], arr[6]} with product 6 ( = 3 * 2 * 1).

Input: arr = {3, 2, 6}
Output: 2

Подход: выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем product , > которая хранит произведение всех элементов массива.
• Пройдите по заданному массиву и найдите произведение всех элементов массива, сохраните его в продукте .
• Инициализируйте две переменные слева и справа равными 1 , в которых хранится произведение левого и правого подмассива.
• Пройдите по заданному массиву и выполните следующие шаги:
  • Умножьте значение left на arr[i] .
  • Разделите значение right на arr[i] .
  • Если значение left равно right , то выведите значение текущего индекса i в качестве результирующего индекса и прервите цикл.
• После выполнения вышеуказанных шагов, если такого индекса не существует, выведите в качестве результата «-1» .

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

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