by Given an array of sizen, the array contains numbers in range from 0 to k-1 wherekis a positive integer and k <= n.
Find the maximum repeating number in this array.
For example:
Input arr = [1,3,4,5,6,7,4]
Maximum occurence element = 4
Maximum occurence = 2
Solution Using Space Complexity O(n) and Time Complexity O(n)
In this solution, we will use a count array which will store the count of occurrence of every number.
Algorithm
- Define a count array of size n with initialized value of 0.
- Traverse the input array and increment the count array as count[arr[i]] += 1
- Traverse the count array and find the index which has the maximum value.
- Index will be the element which has the maximum occurrence
- Value at the index in count array will be the maximum occurrence of the element in the array.
Let’s have a look into the sample code.
void find_max_repeating_number_in_array_using_count ()
{
int arr[MAX_ARRAY_SIZE] = {0};
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
arr[i] = rand() % MAX_ARRAY_SIZE;
}
int count[MAX_ARRAY_SIZE] = {0};
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
count[arr[i]] += 1;
}
int max = 0;
int repeating_item = 0;
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (count[i] > max)
{
max = count[i];
repeating_item = i;
}
}
cout << "Maximum Repeating Element is " << repeating_item << " and instances are " << max << endl;
}
Solution Using Space Complexity O(1) and Time Complexity O(n)
In this solution, we will utilize the existing array memory to find the maximum occurrence element in the array.
Algorithm
- Traverse the input array.
- use absolute value Modulo with k of every element as index and increment the value by k.
- Traverse the input array again and find the index which has the maximum value.
- Index will be the element which has the maximum occurrence
- Value at the index modulo k will be the maximum occurrence of the element in the array.
Let’s have a look into the sample code.
void find_max_repeating_number_in_array ()
{
int arr[MAX_ARRAY_SIZE] = {0};
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
arr[i] = rand() % MAX_ARRAY_SIZE;
}
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
arr[arr[i] % MAX_ARRAY_SIZE] += MAX_ARRAY_SIZE;
}
int max = 0;
int repeating_item = 0;
for (int i = 0; i < MAX_ARRAY_SIZE; i++)
{
if (arr[i] > max)
{
max = arr[i];
repeating_item = i;
}
}
cout << "Maximum Repeating Element is " << repeating_item << " and instances are " << max / MAX_ARRAY_SIZE << endl;
}
Let’s look into a main function which utilizes both the functions.
#define MAX_ARRAY_SIZE 500
int main ()
{
find_max_repeating_number_in_array ();
find_max_repeating_number_in_array_using_count ();
}
Let’s analyze the output of above main function.
Maximum Repeating Element is 340 and instances are 5
Maximum Repeating Element is 21 and instances are 4
