Solution Approach
The solution is simple. We keep a map for the frequency of the powers.
Then, we will traverse the Array from index 2, and keep calculating the different powers of the indexes until we reach the power which is either greater than or equal to the number present on that index. If the calculated power value is greater than the number present at that index, it means that the number present at that index is not a power of the index, so we move to the next index.
Otherwise, if the calculated power value is equal to the number present at that index, increment the power frequency by 1 if it is already present in the map else insert the frequency in the map.
At last, traverse the map once and find out the maximum frequency.
Note: For the indices, 0 and 1, we will not update the frequency of the power initially, because, the numbers 0 and 1 can be found as many different powers of numbers 0 and 1 respectively. For instance, 0^2 = 0, 0^3 = 0 and so on. Similarly, 1^2 = 1, 1^3 = 1 and so one. Therefore, if at index 0, the value is 0, it can be from powering it to many different values apart from 1.
Thus, if at index 0, the value is 0, we will increment the frequency of all the powers apart from 1.
Similarly, for index 1, if the value at it is 1, the power can be any number. Thus, we will just increment the value of the ans by 1 if v[1] = 1.
The steps of implementation are:

Input the Array.

Call the function maxFrequentPower, which returns the maximum frequent power in the Array.
In the maxFrequentPower function:

Declare the hashmap to store the frequency of elements

Iterate the array v from index 2

If the current element is equal to 1, then it's the 0th power of the index. Therefore, increment the frequency of 0 by 1

Declare and initialize a variable power_val to store the power value

Declare a variable to store the power of the index

Keep calculating the further powers of i until the value is smaller than the number at index i.

If the power value is equal to the element at the index, increment the frequency of power by 1 and break out of this loop

Otherwise, move to the next power by incrementing the value of the power

Calculate the next power by multiplying the index by the power value

Now, if v[0] == 1, then increment the frequency of 0 because only 0^0 = 1.

Declare a variable called maxFrequent, which stores the maximum frequency

Now, traverse the map. If v[0] == 0, then increment the frequency of all powers except 0.

If v[0]==0, then update the value of maxFrequent to a maximum of maxFrequent and frequency of current power +1. We are doing this because 0^(anything other than 0) = 0. Otherwise, update maxFrequent to a maximum of maxFrequent and frequency of current power.

Increment the maximum frequency by 1 if v[1] is equal to 1 because 1^(anything) = 1

Return maximum frequency.
 Print the answer returned by the above function.
C++ implementation
#include <bits/stdc++.h>
using namespace std;
int maxFrequentPower(vector<int>& v){
int n = v.size();
// Declare the hashmap to store the frequency of powers
unordered_map<int, int> frequency;
// Iterate the array v from index 2
for (int i=2;i<n;i++){
/*
If current element is equal to 1 then its
the 0th power of the index
*/
if (v[i] == 1){
// Increment the frequency of 0 by 1
frequency[0]++;
continue;
}
/*
Declare and initialize a variable power_val to store the
power value
*/
int power_val = i;
// Declare a variable to store the power of the index
int power = 1;
/*
Keep calculating the further powers of i until, the power value
is smaller than the number at index i
*/
while (power_val <= v[i]){
/*
If the power value is equal to the element at the index,
increment the frequency of power by 1 and break out of this loop
*/
if (v[i] == power_val){
frequency[power]++;
break;
}
// Otherwise, move to the next power by incrementing the value of power
power++;
// Calculate the next power by multiplying index into the power value
power_val*=i;
}
}
// If v[0] == 1, then increment the frequency of 0 because only 0^0 = 1.
if(v[0]==1)
frequency[0]++;
// Declare a variable called maxFrequent which sotres the maximum frequency
int maxFrequent = 0;
// Traverse the map
for (auto it = frequency.begin(); it != frequency.end(); it++){
int power = it>first;
// If v[0] == 0, then increment the frequency of all powers except 0
if (v[0] == 0 && power != 0){
/*
Update the value of maxFrequent to maximum of maxFreuent
and frequency of current power +1. We are doing this, because,
0^(anything other than 0) = 0
*/
maxFrequent = max(maxFrequent, frequency[power] + 1);
}
else{
/*
Otherwise, update maxFrequent to maximum of maxFreuent
and frequency of current power
*/
maxFrequent = max(maxFrequent, frequency[power]);
}
}
/*
Increment the maximum frequency by 1 if v[1] is equal to 1 because,
1^(anything) = 1.
Return maximum frequency
*/
return v[1] == 1 ? maxFrequent + 1: maxFrequent;
}
// Driver function
int main(){
// Input the array
vector<int> v = {0,1,1,9,1,25};
// Print the answer returned by the function
cout << (maxFrequentPower(v))<<endl;
}
You can also try this code with Online C++ Compiler
Run Code
Output
4
You can also try this code with Online C++ Compiler
Run Code
Complexities
Time complexity
O(n*logn), where n is the number of elements in the vector v
Reason: We're traversing the Array once, and in each iteration, we run a while loop until the power value is less than the number at the index. So, the while loop runs for a maximum of logn times. Therefore, for a total of n iterations, the time complexity will be n*logn.
Space complexity
O(1)
Reason: No extra space is taken other than the space of the variables. Thus, the total space complexity is O(1).
You can also read about the Longest Consecutive Sequence.
Frequently Asked Questions
What is HashMap in data structure? Can you provide an example?
A HashMap is a data structure that is able to map certain keys to certain values. The keys and values could be anything.
Where are map data structures used?
The map data structure is used where we want to store a pair of a value and some other value associated with it. This is called a keyvalue pair.
Conclusion
In this article, we discussed the problem of finding the most frequent power if we write the elements present in the Array as powers of theirs indices. The solution to this problem involved the application of maps. It is a very useful data structure in such cases. You can practice more problems based on this data structure. Some of them are Pair sum, Check duplicate, Count distinct substrings, and Maximum frequency number.
Are you planning to ace the interviews with reputed productbased companies like Amazon, Google, Microsoft, and more?
Check out this problem  Pair Sum In Array.
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Happy Coding!