**Problem Link:**

https://www.codechef.com/GHC22019/problems/TOMGRDNR

**Problem:**

Given an array** A** of n numbers where **0<=A[i]<=9** for every valid i (for understanding's sake suppose **0<=i<=n-1**). We need to find the smallest length **x** such that all possible subarrays of array **A** having length **x** have at least one common number.

**Prerequisite:**

Arrays

**Expected Complexity:**

O(n*10)

**Solution:**

Mathematically, the problem says:

find smallest number **x** such that

{A[0], A[1], .., A[x-1]} \(\cap\) {A[1], A[2], .., A[x]} \(\cap\) ... \(\cap\) {A[n-x], A[n-x+1], .., A[n-1]} \(\neq\) \(\phi\) (nothing)

Now, let us call **S** be the intersection set (which is \(\phi\) above).

{A[0], A[1], .., A[x-1]} \(\cap\) {A[0], A[1], .., A[x-1]} \(\cap\) {A[0], A[1], .., A[x-1]} \(\cap\) ... \(\cap\) {A[n-x], A[n-x+1], .., A[n-1]} \(=\) S

Then, **S** can contains multiple numbers.So, we also need to find the smallest number in **x.**

Suppose that smallest number is **p**.

Traverse the array to find the positions of all **p**. Suppose** p **occurs as follows:

X | p | p | X | X | p | X | p | X | X | X |

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

**p** occurs at *1,2,5,7*. From the positions we can see that between* 5* and *7* the gap is maximum. So, a** p** always occurs in a subarray of length *3 (7-5+1=3. a subarray of length 3).* But we are ignoring the gap at the beginning and at the end. The first **p** occurs at index* 1* but the last **p** occurs at index *7*. So, the gap is maximum towards the end which is *10-7+1=4*. So, we can say that a **p** always occurs in a subarray of length *4* in this case. Now, we can generalise it and solve for all p between 0 and 9 to get the answer.

Here in the solution, we store positions of p in v[p]. If v[p] is empty, then there p can't be that common flower. So, we search for another p. mx[p] will store the maximum subarray size for a particular p such that every subarray of size mx[p] contains a flower of type p. Finally we find minimum of all mx[p] and get the answer.

```
int n;
cin >> n;
int a[n];
vector<int> v[10];
for (int i = 0; i < n; i++) {
cin >> a[i];
v[a[i]].push_back(i);
}
int mx[10], res_len = n + 10, res_num = -1;
for (int i = 0; i < 10; i++) {
if (v[i].empty())
continue;
mx[i] = max(v[i].front() + 1, n - v[i].back());
for (int j = 1; j < v[i].size(); j++) {
mx[i] = max(mx[i], v[i][j] - v[i][j - 1]);
}
if (mx[i] < res_len) {
res_len = mx[i];
res_num = i;
}
}
cout << res_len << " " << res_num;
```

**Solution Link:**

Author's : https://www.codechef.com/viewsolution/24044636