The Food Inspector

Input: ‘N’ = 2, ‘M' = 2, ‘ARR1’ = [{“bread”, 10}, {“rice”, 20}], ‘ARR2’ = [{“milk”, 25}, {“rice”, 20}] Output: 0 In this case, here the only same product in both shops is “rice” and the price is the same in both shops (i.e. 20). Thus there is no product with the same name but at different prices.

The first line will contain the integer ‘T’, the number of test cases. The first line of each test case contains two integers, ‘N’ and ‘M’ separated by spaces. Followed by ‘N’ lines, each containing the name of the product ‘foodItem’ and the non-negative integer price of the products ‘P’, denoting the food products of the shop ‘A’. Followed by ‘M’ lines, each containing the name of the product ‘foodItem’ and the non-negative integer price of the products ‘P’, denoting the food products of the shop ‘B’.

1 <= ‘T’ <= 10 1 <= ‘N’ <= 10^4 1 <= ‘M’ <= 10^4 It is guaranteed that ‘foodItem’ consists of only lower-case English letters. It is guaranteed that the length of ‘foodItem’ is less than ‘10’. It is guaranteed that the name (i.e. ‘foodItem’) of every product in a single shop is distinct. 0 <= ‘P’ <= 10^9 It is guaranteed that sum of the lengths of ‘foodItem’ is <= 10^5. It is guaranteed that sum of ‘N’ over all test cases is <= 10^4 It is guaranteed that sum of ‘M’ over all test cases is <= 10^4 Time Limit: 1 sec

For the first test case, “wheat” has a price of ‘10’ in shop ‘A’ and ‘15’ in shop ‘B’, other products have the same price. Hence, the output will be: 1 For the second test case, “onion” has a price of ‘1’ in shop ‘A’ and ‘80000’ in shop ‘B’. Hence, the output will be: 1

Brute Force

The idea for this approach is to iterate on the products of any shop and try to find a product with the same name in another shop and match their prices.

So we can keep a variable ‘count’, denoting the number of unmatched products price, initially set to 0. Now we iterate on the products of shop ‘A’ (i.e. iterate on the array ‘ARR1’) and for each ‘i’ ∈ ‘[0, N-1]’ we try to find the product in shop ‘B’ (i.e. ‘ARR2’) that has the same name as ‘ith’ product of shop ‘A’ but have different price. If we find such a product in shop ‘B’ we increment the ‘count’ by ‘1’ otherwise if there exists a product with the same name and the same price or product with that name doesn’t exist we move to the next product.

Algorithm:

// The function will return the count of products with the same name and different prices.

Int differentPrices(N, M, ARR1, ARR2)

Initialize the variable named ‘COUNT’ with the value of ‘0’.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize the variable named ‘prodNameA’ with the value of the first of the pair ‘ARR1[i]’.
- Initialize the variable named ‘prodPriceA’ with the value of the second of the pair ‘ARR1[i]’.
- Run a for loop from ‘0’ to ‘M-1’ with a variable named ‘j’.
  - Initialize the variable named ‘prodNameB’ with the value of the first of the pair ‘ARR2[j]’.
  - Initialize the variable named ‘prodPriceB’ with the value of the second of the pair ‘ARR2[j]’.
  - If ‘prodNameA == prodNameB’
    - If ‘prodPriceA == prodPriceB’
      - Increment ‘COUNT’ by ‘1’.
    - Stop the loop.
Return ‘COUNT’

Time Complexity

O( N * M * L ), Where ‘N’ and ‘M’ are input integers and ‘L’ denotes the longest name of any food item.

In the above algorithm, in the worst case when no products of either shop are the same, for every product of shop ‘A’ we will iterate through every product of shop ‘B’ and we will compare both the product names, which in the worst case can take ‘L’ comparisons when both names are equal, in total ‘N*M*L’ iterations.

Hence the time complexity will be O( N * M * L )

Space Complexity

O( 1 ),

In the above algorithm, we use the variable ‘COUNT’ and some temporary loop variables only.

Hence the space complexity will be O( 1 ).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation Of Sample Input 1 :

Sample Input 2 :

Sample Output 2 :