> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/n-3-repeat-number.md).

# N/3 Repeat Number

You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space.

If so, return the integer. If not, return -1.

If there are multiple solutions, return any one.

**Example :**

```
Input : [1 2 3 1 1]
Output : 1 
1 occurs 3 times which is more than 5/3 times. 
```

```java
public class Solution {
    public int repeatedNumber(final List<Integer> arr) {
        int n = arr.size();
        int count1 = 0, count2 = 0;
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (first == arr.get(i))
                count1++;
            else if (second == arr.get(i))
                count2++;
            else if (count1 == 0) {
                count1++;
                first = arr.get(i);
            } else if (count2 == 0) {
                count2++;
                second = arr.get(i);
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < n; i++) {
            if (arr.get(i) == first)
                count1++;
            else if (arr.get(i) == second)
                count2++;
        }
        if (count1 > n / 3)
            return first;
        if (count2 > n / 3)
            return second;
        return -1;
    }
}
```