Проверьте, является ли произведение всех элементов массива идеальным квадратом или нет.
Дан массив 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)