Find the Highest Frequency of Non-Negative Powers that are the Same as Indices of Elements in the given Array

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 key-value 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 product-based 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:

• Top Array Coding Interview Questions
• Find All Duplicates in an Array
• Reduce Array Size to Half
• Longest Substring Without Repeating Characters

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!