Given an array of integers of size `n`

, we have to find out if any integer occurs more than `n/3`

times in the array in linear time and constant extra space. If we find an element then print the element else print `-1`

.

## Scope

This article tells about Moore’s Voting Algorithm

In this article we will learn implementation of Moore’s Voting Algorithm.

In this article we will learn complexity of Moore’s Voting Algorithm.

## Takeaways

Moore’s Voting algorithm takes `O(N)`

time complexity and `O(1)`

space complexity.

## Example

**Input :** [4,2,3,2,1,2,2,4]**Output :**

`2`

**Input :** [1,7,7,1,2,3]**Output :**

`-1`

## Explanation

- In the first example, we can see that
`n = 8`

, so there must be an element that occurs more than`8/3 = 2`

times (we will take the floor value). We can see that frequency of`2`

is`4`

which is more than`2`

, so in this case, we will print`2`

. - In the second example, we can see that
`n = 6`

, so there must be an element that occurs`6/3 = 2`

times (we will take the floor value). We can see that frequency of all the elements in the array is less than or equal to`2`

, so in this case, we will print`-1`

.

## Constraints

$3 <= N <= 10000$

$1 <= A[i] <= 10000$

## Approach: Using Moore’s Voting Algorithm

We have many approaches for finding the `n/3`

repeat number, with different time and space complexities.

But this algorithm `(Moore's voting algorithm)`

can find the `n/3`

repeat number in just linear time complexity and constant extra space.

This algorithm works on the concept that there will be a maximum of two numbers which can occur more than `n/3`

times, we can understand the basic maths behind this as shown below:

### Proof of Moore’s Voting Algorithm

Let’s assume that there are three `n/3`

repeat numbers in the array, so let’s consider the minimum frequency that these three numbers can have which is `n/3+1`

each. Now let’s add the frequency of these three numbers, we know that the sum of the frequencies must be less than or equal to n, but

$$(\frac{n}{3} + 1) + (\frac{n}{3} + 1) + (\frac{n}{3} + 1) = \frac{3n}{3} + 3$$

$$n + 3 <= n$$ (which is not possible for any integer n)

Now let’s assume that there are two $\frac{n}{3}$ repeat numbers in the array, so let’s consider the minimum frequency that these two numbers can have which is $\frac{n}{3}+1$ each. Now let’s add the frequency of these two numbers, we know that the sum of the frequencies must be less than or equal to n, and

$$(\frac{n}{3} + 1) + (\frac{n}{3} + 1) = \frac{2n}{3} + 2$$

$$\frac{2n}{3} + 2 <= n$$ (which can be possible for integers greater than 3)

Now let’s assume that there is one $\frac{n}{3}$ repeat number in the array, so let’s consider the minimum frequency that this number can have which is $\frac{n}{3}+1$. Now let’s see the frequency of this number, we know that the frequency of this number must be less than or equal to n, and

$$(n/3 + 1)$$

$$n/3 + 1 <= n$$ (which is possible for every integer n)

So, here is a brief, on what we will do in the algorithm

- We will assume that there could be a maximum of two $\frac{n}{3}$ repeat numbers, and now our task is to find out the frequencies of these possible two $\frac{n}{3}$ repeat numbers.
- After finding the frequencies, we will check if any of these two numbers have a frequency greater than $\frac{n}{3}$, we will return this number
- But if both the numbers are having a frequency less than or equal to $\frac{n}{3}$, we will return -1.

### Algorithm

- Let us assume we are given an array
**nums with size**.`n`

- Create
`4`

variables, two for the elements and two for their frequencies. - Initialize them as
`count1 = 0`

,`count2 = 0`

,`num1 = -1`

,`num2 = -1`

- Now run a for loop from
`i=0`

to`i=n-1`

and do one of the following- if
`a[i]`

is equal to`num1`

, then increase the frequency of the first number - else if
`a[i]`

is equal to`num2`

, then increase the frequency of the second number - else if
`count1`

is equal to`0`

, then initialize the first number as`a[i]`

and increase its frequency - else if
`count2`

is equal to`0`

, then initialize the second number as`a[i]`

and increase its frequency - else decrease the frequency of both the numbers

- if
- Now make the
`count1`

and`count2`

again zero - Again run a for loop from
`i=0`

to`i=n-1`

- If
`a[i]`

is equal to`num1`

, increase its frequency - If
`a[i]`

is equal to`num2`

, increase its frequency - After the loop is over, check the frequency of the numbers, if any of these numbers have a frequency greater than $\frac{n}{3}$, then return this number, else return
`-1`

.

### C++ Implementation

```
#include<bits/stdc++.h>
using namespace std;
int Nby3RepeatNumber(vector<int> nums,int n){
int count1 = 0, count2 = 0, num1 = -1, num2 = -1, i;
for(i = 0 ; i < n ; i++){
if(nums[i] == num1){
```*// num1 is already equal to nums[i],*
count1 = count1 + 1; *// so we will increase its frequency by 1*
}
else if(nums[i] == num2){ *// num2 is already equal to nums[i],*
count2 = count2 + 1; *// so we will increase its frequency by 1*
}
else if(count1 == 0){ *// frequency of num1 is 0, it means num1 is not initialized till now, *
num1 = nums[i]; *// so we will initialize it with nums[i] and increase its frequency by 1*
count1 = count1 + 1;
}
else if(count2 == 0){ *// frequency of num1 is 0, it means num1 is not initialized till now,*
num2 = nums[i]; *// so we will initialize it with nums[i] and increase its frequency by 1*
count2 = count2 + 1;
}
else{
count1 = count1 - 1; *// If none of the statements holds true, *
count2 = count2 - 1; *// deacrease the frequency of both num1 and num2 *
}
}
count1 = 0;
count2 = 0;
for (i = 0 ; i < n ; i++) {
if (nums[i] == num1){
count1 = count1 + 1;
}
else if (nums[i] == num2){
count2 = count2 + 1;
}
}
if (count1 > n / 3){ *// If frequency of num1 > n/3, return num1*
return num1;
}
else if (count2 > n / 3){ *// If frequency of num2 > n/3, return num2*
return num2;
}
else{
return -1; *// no element is having frequency > n/3, so return -1;*
}
}
int main(){
vector<int> nums{4,2,3,2,1,2,2,4};
int n = nums.size();
int num = Nby3RepeatNumber(nums,n);
if(num != -1){
cout<<"n/3 repeat number is "<<num;
}
else{
cout<<"n/3 repeat number does not exist in the array";
}
return 0;
}

### Java Implementation

```
public class Main {
public static int Nby3RepeatNumber(int nums[], int n)
{
int count1 = 0, count2 = 0, num1 = -1, num2 = -1, i;
for(i = 0 ; i < n ; i++){
if(nums[i] == num1){
```*// num1 is already equal to nums[i],*
count1 = count1 + 1; *// so we will increase its frequency by 1*
}
else if(nums[i] == num2){ *// num2 is already equal to nums[i],*
count2 = count2 + 1; *// so we will increase its frequency by 1*
}
else if(count1 == 0){ *// frequency of num1 is 0, it means num1 is not initialized till now, *
num1 = nums[i]; *// so we will initialize it with nums[i] and increase its frequency by 1*
count1 = count1 + 1;
}
else if(count2 == 0){ *// frequency of num1 is 0, it means num1 is not initialized till now,*
num2 = nums[i]; *// so we will initialize it with nums[i] and increase its frequency by 1*
count2 = count2 + 1;
}
else{
count1 = count1 - 1; *// If none of the statements holds true, *
count2 = count2 - 1; *// deacrease the frequency of both num1 and num2 *
}
}
count1 = 0;
count2 = 0;
for (i = 0 ; i < n ; i++) {
if (nums[i] == num1){
count1 = count1 + 1;
}
else if (nums[i] == num2){
count2 = count2 + 1;
}
}
if (count1 > n / 3){ *// If frequency of num1 > n/3, return num1*
return num1;
}
else if (count2 > n / 3){ *// If frequency of num2 > n/3, return num2*
return num2;
}
else{
return -1; *// no element is having frequency > n/3, so return -1;*
}
}
public static void main(String[] args)
{
int nums[] = {4,2,3,2,1,2,2,4};
int n = nums.length;
int num = Nby3RepeatNumber(nums, n);
if(num != -1){
System.out.print("n/3 repeat number is "+num);
}
else{
System.out.print("n/3 repeat number does not exist in the array ");
}
}
}

### Python Implementation

```
def Nby3RepeatNumber(nums, n):
count1 = 0
count2 = 0
num1 = -1
num2 = -1
for i in range(0,n):
if(nums[i] == num1):
```*# num1 is already equal to nums[i],*
count1 = count1 + 1 *# so we will increase its frequency by 1*
elif(nums[i] == num2): *# num2 is already equal to nums[i],*
count2 = count2 + 1 *# so we will increase its frequency by 1*
elif(count1 == 0): *# frequency of num1 is 0, it means num1 is not initialized till now, *
num1 = nums[i]; *# so we will initialize it with nums[i] and increase its frequency by 1*
count1 = count1 + 1
elif(count2 == 0): *# frequency of num2 is 0, it means num1 is not initialized till now, *
num2 = nums[i]; *# so we will initialize it with nums[i] and increase its frequency by 1*
count2 = count2 + 1
else:
count1 = count1 - 1 *# If none of the statements hold, *
count2 = count2 - 1 *# deacrease the frequency of both num1 and num2 *
count1 = 0;
count2 = 0;
for i in range(0,n):
if (nums[i] == num1):
count1 = count1 + 1
elif (nums[i] == num2):
count2 = count2 + 1
if (count1 > n / 3): *# If frequency of num1 > n/3, return num1*
return num1;
elif (count2 > n / 3): *# If frequency of num2 > n/3, return num2*
return num2;
else: *# no element is having frequency > n/3, so return -1;*
return -1
nums = [4,2,3,2,1,2,2,4]
n = len(nums)
num = Nby3RepeatNumber(nums, n)
if(num != -1):
print("n/3 repeat number is ", num)
else:
print("n/3 repeat number does not exist in the array ")

### Output

```
n/3 repeat number is 2
```

## Complexity Analysis

### Time Complexity Analysis

- In the first step, we are running a loop from i=0 to
`i=n-1`

which takes**O(N)**time - In the second step, we are again running a loop from
`i=0`

to`i=n-1`

which takes**O(N)**time - So the total worst-case time complexity for this approach to find the $\frac{n}{3}$ repeat number is O(N) + O(N) =
**O(N)**

### Space Complexity Analysis

- In this approach, we are using only
`4`

variables, which is considered as constant space, so the space complexity of this approach is**O(1)**. **Time Complexity: O(N)****Space Complexity: O(1)**

## Conclusion

- In this quick tutorial, we have discussed Moore’s Voting algorithm which takes just
**O(N)**time complexity and**O(1)**space complexity. - Moore’s voting algorithm is the best algorithm to find the $\frac{n}{3}$ repeat number as it uses the fact that there can be at most two numbers that can have a frequency greater than $\frac{n}{3}$. We have also seen the proof of this algorithm in the article.