n/3 Repeat Number

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

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.

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

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)