Проверьте, является ли произведение всех элементов массива идеальным квадратом или нет.

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

Примеры:

Input: arr[] = {1, 4, 100}
Output: Yes
Explanation: The product of all the numbers is 1 x 4 x 100 = 400 which is a perfect square. Therefore, print “Yes”.

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

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

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

• Создайте частотный массив , чтобы хранить полномочия простых факторов.
• Начните обход массива.
• Для каждого элемента arr[i] используйте решето Эратосфена, чтобы найти степени простых множителей arr[i] и добавить их в массив частот.
• После обхода массива начните обход массива частот .
• Если какой-либо элемент (кроме 1) имеет нечетную частоту , верните false , иначе верните true.

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

Временная сложность: O(N * log X), где X — самый большой элемент массива.
Вспомогательное пространство: O(N)