1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Why does it work?
2.2.
Algorithm
2.3.
Implementation in C++
2.4.
Implementation in Python
2.4.1.
Time Complexity
2.4.2.
Space Complexity
3.
3.1.
What is greedy in coding?
3.2.
What is time and space complexity?
3.3.
What does O(1) space mean?
4.
Conclusion
Last Updated: Mar 27, 2024

# Find the Maximum Repeating Number in O(N) Time and O(1) Extra Space

## Introduction

In this blog, we will take up a coding challenge which is seemingly very easy to complete. However, it becomes increasingly difficult to solve the problem when the constraints are put forward. We will find the maximum repeating element in the array and try to come up with a solution within the given constraints. Apart from this, we will also discuss the easy-approaches to solve the problem but outside of the constraints.

### Problem Statement

Ninja has given you an array of size N and a number K. It is assumed that all elements in the array are in the range [0, K - 1] and K <= N. Your task is to find the maximum repeating element in the array in O(N) time and O(1) space. So without wasting time, let’s get started.

### Sample Examples

Input

Enter the size of the array: 5

Enter the elements of the array (space-separated): 2 2 1 3 4

Enter the value of K: 5

Output: 2

Explanation: As it is visible, 2 is the maximum repeating element, occurring twice.

Input 2

Enter the size of the array: 7

Enter the elements of the array (space-separated): 3 2 1 3 4 1 3

Enter the value of K: 6

Output: 3

Explanation: As it is visible, 3 is the maximum repeating element, occurring thrice.

Also see, Euclid GCD Algorithm

## Approach

Naive Approach: If we forget the constraints for a moment, we could find the maximum repeating element in a variety of ways. We could run two for loops (nested) over the array elements and count the occurrences of each array element in each iteration of the inner for loop. Then we can find the element with the highest number of occurrences. The time complexity of this approach is, however, O(N ^ 2) and space complexity is O(1), where N is the size of the input array.

Efficient Approach: To improve the time complexity of finding the maximum repeating element, we can create an array FREQ of size K. Now, we can loop over the array elements and increment FREQ[ARR[IND]] by one, where ARR is the input array and IND is the iterator. We can do this because it is given that all elements of the array are less than K. Now, we can simply pick the index with maximum value and output it as the maximum repeating element. But again, the time complexity of this approach is O(N) (great improvement!) and the space complexity is O(K) due to the FREQ array so created.We missed it by a little margin!

So let us now discuss the final solution to find the maximum repeating element. We can iterate over the input array ARR and increment ARR[ARR[IND] % K] by K, where IND is the iterator. Now, we can output the index with the maximum value as the answer. Time and Space complexity are within the constraints, i.e., O(N) and O(1) respectively.

### Why does it work?

Few points to keep in mind:

1. By incrementing the array elements by K, we are not changing the value of this expression: ARR[IND] % K.
2. The element with most occurrences will have its index incremented the most number of times.
3. Since all the elements are below K, we can identify the maximum repeating element by the index which holds the maximum value. As maximum value is analogous to maximum number of increments.

### Algorithm

1. Take the input array and the value of K.
2. Iterate over the array with IND as the iterating variable.
1. Increment ARR[ARR[IND] % K] by K.
3. Find the index with maximum value and output the index as the answer.

### Implementation in C++

``````// C++ Program to find the maximum repeating element in O(N) time and O(1) space.
#include <bits/stdc++.h>
using namespace std;

// Function to solve the problem.
int solve(vector<int> &arr, int n, int k)
{
// Current ans = 0;
int ans = 0;

// Current maximum element.
int currMax = -1;
for (int i = 0; i < n; i++)
{
// As discussed in the approach.
arr[arr[i] % k] += k;

// Update the ans and currMax variables if satisfied.
if (arr[arr[i] % k] > currMax)
{
currMax = arr[arr[i] % k];
ans = arr[i] % k;
}
}

// Return the ans.
return ans;
}

int main()
{
// Input the array and K.
int n;
cout << "Enter the size of the array: ";
cin >> n;
cout << "Enter the elements of the array (space-separated): ";
vector<int> arr;
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
arr.push_back(a);
}
int k;
cout << "Enter the value of K: ";
cin >> k;
cout << solve(arr, n, k);
}``````

### Implementation in Python

``````// Python Program to find the maximum repeating element in O(N) time and O(1) space.
# Take the input.
print("Enter the size of the array: ", end="")
n = int(input())

print("Enter the elements of the array (space-separated): ", end="")
arr = [int(i) for i in input().split()]

print("Enter the value of K: ", end="")
k = int(input())

# Current max element and the answer.
maxElem = -1
ans = 0

# Iterate through the array.
for i in range(n):
# As discussed in the approach.
arr[arr[i] % k] = k

# If required, update the maxElem and ans variables.
if arr[arr[i] % k] > maxElem:
maxElem = arr[arr[i] % k]
ans = arr[i] % k

# Print ans.
print(ans)``````

Input

Enter the size of the array: 5

Enter the elements of the array (space-separated): 2 2 1 3 4

Enter the value of K: 5

Output

2

#### Time Complexity

The Time Complexity of the above approach is O(N), where N is the size of the array.

It is because we are iterating the array in a single for loop and doing the O(1) operations. Also, the time complexity of finding the index holding the maximum element is O(N).

#### Space Complexity

The Space Complexity of the above approach is O(1), as we are not using any extra space.

### What is greedy in coding?

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are best fit for Greedy.

### What is time and space complexity?

Time complexity is the time taken by the algorithm to execute each set of instructions. It is always better to select the most efficient algorithm when a simple problem can solve with different methods. Space complexity is usually referred to as the amount of memory consumed by the algorithm.

### What does O(1) space mean?

It means the space required by the algorithm to process data is constant; it does not grow with the size of the data on which the algorithm is operating.

## Conclusion

In this blog, we discussed an exciting question, which was simple to solve but without the constraints. Coding Ninjas hopes to deliver the solution in the best possible way and believes that you have learned something new today.

If you would like to follow more articles on such topics, please refer to these links. Linked ListDSAArray Coding Questions, Stack ImplementationQueues, and much more.

You can also refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass