N/3 Repeat Number

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
• 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.