Find the highest frequency of non-negative powers that are the same as indices of elements in the given array

Shreya Deep
Last Updated: May 13, 2022

Introduction

In this article, we will be discussing a problem in which we have to find the frequency of the power which occurs highest times if we write the number present at an index of an array as some power of that index.

To find each number's frequency in a group of numbers, we often use maps in c++. We put the number and frequency as the key-value pair in a map. We will use this method in our solution.

Problem Statement

You are given an array of numbers, and you have to find the frequency of the power which occurs highest times if we write the number present at an index of an array as some power of the index.

Note: If there are multiple answers, return the smallest of them.

For example:

Input

Array = [0,1,1,9,1,25]

Output

4

Explanation

For index 0, 0 can be any power of 0 other than 1. So, if the maximum frequency number is another 1, we will increment its count by 1 in the end. 

For index 1, again, one can be any power of 1. So, we will increment the answer count by 1 in the end.

For index 2, only 2^0 can be 1. Thus, increase the count of 0 by 1.

For index 3, 3^2 = 9. Thus, increase the count of 2 by 1.

For index 4, only 4^0 = 1. Thus, increase the count of 0 by 1.

For index 5, 5^2 = 25. Thus, increase the count of 2 by 1.

If we consider indexes, 2,3,4, and 5, right now, we have, frequency(2) = 2, and frequency(0) = 2. So, since 0 is the smaller one, we will assign the power for index 0 as 0. Similarly, since 1^0 = 1, we will assign the power for index 1 to 0. Therefore, frequency(3) = 4 will be the maximum frequency. Thus, 4 will be the answer. 

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. 

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 power
       
    • Calculate the next power by multiplying the index into 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;
}


Output

4

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 interations, 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).

Frequently asked questions

  1. 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.
     
  2. Where are map data structures used?
    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.

Key Takeaways

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 sumCheck duplicateCount distinct substrings, and Maximum frequency number.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on CodeStudio now!

Happy Coding!

Was this article helpful ?
0 upvotes