10 weeks ago

Rohit • 610

Hyderabad

Question 1

You are given two lists of positive integers. Write an algorithm representing the number of elements in the first list(N).

Input

The first line of the input consists of an integer - listinput1_size, representing the number of elements in the first list(N).

The second line consists of N space separated integers representing the first list of integers.

The third list of an integer - listinput2_size, representing the number of elements in the second list(M).

The last line consists of M space-separated integers representing the second list of positive integers.

Output

Print a positive integer representing the count of elements that are both the lists of integers.

Example

Input

11
1  1  2  3  4  5  5  7  6  9  10
10
11  12  13  4  5  6  7  18  19  20

Output:

12

Explanation:

The numbers that are not common to both lists are [1, 1, 2, 3, 9, 10, 11, 12, 13, 18, 19, 20]

So, the output is 12.

Question 2

A company sells its products at N outlets are connected to each other by a series of roads. There is only one way to reach from one outlet to another. Each outlet of the company has a unique outlet ID. Whenever the inventory of a certain product reaches a minimum limit then K outlets make a request for extra inventory. The company sends the requested products from its warehouse to the outlets. In order to save on fuel, the warehouse supervisor directs the driver Mike ti deliver the products to the outlets along the shortest and most direct path possible, without traveling any single road twice.

Write an algorithm to help Mike deliver his inventory to the maximum number of outlets without traveling any road twice.

Input

The first line of the input consists of an integer - num, representing the total number of outlets of the company including the warehouse(N).

The second line consists of koutletsCount, representing the outlets that requested the extra inventory(K).

The third line consists of K space-separated integers representing the outletIDs of the outlets that requested the extra inventory.

The fourth line consists of two space-separated integers - numR and conOutlet representing the total number of roads between two outlets including the warehouse(numR(M) is always equal to N-1) and the number of outlets connected by a road (conOutlet(X) is always equal to 2).

Output

Print an integer representing the maximum number of outlets that Mike can cover in a single trip without traveling any road twice.

Constraints

• 0 <= koutletsCount <= 10^5
• 1 <= num <= 10^5
• 1 <= A, B <= num; where a, B represent the outlets connected a road
• numR=num-1

Example

Input

4
3
2  3  4
3  2
1  2
1  3
1  4

Output

2

Explanation

In a single trip Mike can reach only two outlets i.e. [2,3] or [2,4] or [3,4] because in order to reach the third outlet he would have to travel one road twice, which he cannot do.

So, the output is 2.

11 months ago

Manas 310

Bānswāra

Question 1

The Question can be easily solved using a hash_map. We would maintain 2 hash maps for each array. In each hash_map we will store if the number has occurred in the array or not (instead of a hash_map, even a set can be used). We will find the uncommon elements by checking the ones which occur in one hash map but do not occur in the other. The number of such elements would directly give us the answer.

Below is the cpp pseudo code for the same :

int ans = 0;
for(auto i : arr1)
{
    if(mp2.find(i) == mp2.end())
    {
        ans++;
    }
}
for(auto i : arr2)
{
    if(mp1.find(i) == mp1.end())
    {
        ans++;
    }
}