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

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

Примеры:

Input: arr[] = {1, 4, 100}
Output: Yes
Explanation:
Following are the subsequences of the given array arr[]:

1. {1}, the product is equal to 1, and is a perfect square.
2. {1, 4}, the product is equal to 4, and is a perfect square.
3. {1, 100}, the product is equal to 100 and is a perfect square.
4. {1, 4, 100}, the product is equal to 400 and is a perfect square.
5. {4}, the product is equal to 4 and is a perfect square.
6. {4, 100}, the product is equal to 400 and is a perfect square.
7. {100}, the product is equal to 100 and is a perfect square.

Therefore, print “Yes”.

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

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

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

Эффективный подход. Приведенный выше подход также можно оптимизировать, используя тот факт, что произведение двух чисел с полным квадратом также будет идеальным квадратом. Поэтому, чтобы проверить, является ли индивидуальное произведение элементов всех подпоследовательностей идеальным квадратом или нет, идея состоит в том, чтобы проверить, являются ли все элементы массива идеальными квадратами или нет. Если найдено верно, то выведите Yes . В противном случае выведите Нет .

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

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