Найти максимальную частоту неотрицательных степеней, которые совпадают с индексами элементов в данном массиве
Дан массив arr[] с N неотрицательными целыми числами, найдите максимальное количество элементов, которые имеют одинаковые неотрицательные степени своих индексов.
arr[i] = iX, where X is a non negative number.
Задача — вернуть максимальную частоту X.
Пример:
Input: arr = [1, 1, 4, 17]
Output: 2
Explanation:
The element 1 at index 0, is a power of 0
The element 1 at index 1, is a power of 0
The element 4 at index 2, is a power of 2
The element 17 at index 3, is not a power of its index, so it is not considered
Therefore the maximum frequency is of power 0, which is 2Input: arr = [0, 1, 1, 9, 1, 25]
Output: 4
Explanation:
The element 0 at index 0, is a power of 2
The element 1 at index 1, is a power of 2
The element 1 at index 2, is a power of 0
The element 9 at index 3, is a power of 2
The element 1 at index 4, is a power of 0
The element 25 at index 5, is a power of 2
Therefore the maximum frequency is of power 2, which is 4
Подход: Данную проблему можно решить, найдя степени каждого индекса и проверив, равны ли они элементу, присутствующему в этом индексе.
Выполните следующие шаги, чтобы решить проблему:
- Итерировать массив arr от индекса 2 до конца и по каждому индексу:
- Используйте цикл для умножения индекса на себя, пока значение не станет меньше максимального значения целого числа и меньше или равно элементу, присутствующему в этом индексе.
- Если мощность становится равной элементу, проверьте, присутствует ли он в хэш-карте:
- Если мощность отсутствует, добавьте ее в хеш-карту со значением 1.
- В противном случае, если мощность уже присутствует, увеличьте ее частоту на 1.
- Если мощность становится равной элементу, проверьте, присутствует ли он в хэш-карте:
- Используйте цикл для умножения индекса на себя, пока значение не станет меньше максимального значения целого числа и меньше или равно элементу, присутствующему в этом индексе.
- Если arr[0] = 1, то увеличить частоту 0 в хэш-карте на 1
- Повторите HashMap и найдите значение с максимальной частотой:
- Если arr[0] = 1, то частота всех значений, кроме 0, увеличивается на 1
- Если arr[1] = 1, то вернуть maxFreq +1, иначе вернуть maxFreq
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * log N)
Вспомогательное пространство: O(1)