n/3 Repeat Number

Example

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

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

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

Java Implementation

Python Implementation

Output

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)