### PROBLEM LINK:

**Author:** Roman Rubanenko

**Tester:** Shiplu Hawlader

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

Cakewalk

### PREREQUISITES:

Simple Array.

### PROBLEM:

For a given array, you can copy one segment of the array and paste it anywhere.

You are given the final array A after copy paste operations, find the minimum size of initial array.

### Explanation

*It looks like answer of the problem is number of distinct number in the array.*

Yes, you are right. Let us prove it.

If the initial array is containing all the distinct numbers, we can generate our

the array A by applying copy paste operations.

We will simply iterate over each distinct numbers and place it in its correct positions. You can see

its resemblance with insertion sort.

*Can you take some example?*

Yes, take the example. Let A = [3 1 2 1 2 3].

Let assume that our initial array is a: Initially it will contain all the distinct elements ie. a = [1 2 3].

Now let us iterate over each distinct numbers.

Start with 1.

Add 1 between 1 and 2.

a = [1 1 2 3]

Now we go to 2.

Add 2 between 1 and 1.

a = [1 2 1 2 3]

Now we go to 3.

Add 3 in the beginning.

a = [3 1 2 1 2 3]

Now we notice that we have generated the array we wanted to generate ie. a is same as A.

*Got it, How to find number of distinct numbers in the array?*

Finding number of distinct numbers in array can be done by following ways.

- As the range of integers in A is small (1 <= A[i] <= 10^5). So we can create a lookup array and update the information of numbers in a single pass of the

array. Let us say lookup array is denoted by cnt. We will iterate over the array and update the cnt of the numbers. Finally number of distinct numbers will be

equal to positions having their cnt values positive. - Using set in C++. We can use HashSet, TreeSet etc in Java.

**Pseudo Code 1**

```
// create the lookup array and initialize it with value 0;
int cnt[100001] = {0}
for (int i = 0; i < n; i++)
{
// update the cnt array
cnt[A[i]]++;
}
int ans = 0;
for (int i = 1; i <= 100000; i++)
if (cnt[i] > 0)
ans++;
```

**Pseudo Code 2**

```
set<int> s;
for (int i = 0; i < n; i++)
st.insert(A[i]);
int ans = st.size();
```

**Few Small Points**

- Array of size cnt should be 10^5 + 1, not 10^5.

**Complexity**:

In case of using set, Each insertion option takes O(log n) times, So overall time complexity for n insertions will be O(n log n).

In case of using lookup array, We just need a single pass over the array A and then we need to check for 10^6 values whether they cnt value is positive

or not. So overall time complexity will be O(max(n, 10^5)).