Count items common to both the lists but with different prices

Difficulty Level Easy
Frequently asked in Amazon Factset GE Healthcare Honeywell TCS Tesla
Binary Search Hash Hashing SearchingViews 3418

Problem Statement

You are given two lists. Each of which index contains the name of the item and its price. The problem statement asks to count items common to both the lists but with different prices, which is to find out how many numbers of items are common in both of the given lists and also at different prices.

Example

List1[] = {{"egg", 60}, {"butter", 20}, {"rice", 50}, {oil", 30}}

List2[] = {{“butter", 20}, {"egg", 15},{"wheat", 40}, {"rice", 60}}
2

Explanation: Only egg and rice are the two elements which are common in both of the lists and with different price.

Algorithm to count items common to both the lists but with different prices

1. Declare a map and set the value of output to 0.
2. Store the first list’s name and its price to the map.
3. Traverse the second list.
    1. Check for the second list’s element, if each element’s name of the second list has a common value in list1’s name.
    2. Check for if that particular element’s price should not be equal to the element price in list1.
        1. If true, then increase the count of output by 1.
4. Return output.

Explanation

Count items common to both the lists but with different prices

We have given two lists, each of the lists contains the two columns value, contains the name of any item and its price. The task is to find out the common elements in both of the lists and also their prices should not be equal to each other respect to the elements. We are going to use hashing and an extra class or structure, also hashing provides an efficient solution.

We will be using an object list. It will ease our job. We will make the list of object type and each of the objects contains its two properties, properties are the name of the item and its price. If we have two lists, so for each index we can take two values and each index behave like an object and we can have the values in that object. So what we are going to do is traverse the first list and store each element in map, with its name as key and price as value. So now the first list’s all elements are all in the map.

We will be traversing the second list and picking up each element of the list, now we have the map and in that first list and its names prices are stored. So we will just check for if the current element list’s name is available in the map if true then we will check for the price associated with that element is not equal to map’s value which we have already stored. If all of these conditions are true then simply increase the count of output by 1, because we just have to count the number of items and we are doing with that counting the number of that common item and its price.

Code to count items common to both the lists but with different prices

C++ code

#include<iostream>
#include<unordered_map>

using namespace std;

struct item
{
    string name;
    int price;
};
int getItemCount(item list1[], int m,item list2[], int n)
{
    unordered_map<string, int> MAP;
    int output = 0;

    for (int i = 0; i < m; i++)
        MAP[list1[i].name] = list1[i].price;

    for (int i = 0; i < n; i++)
        if ((MAP.find(list2[i].name) != MAP.end()) &&(MAP[list2[i].name] != list2[i].price))
            output++;

    return output;
}
int main()
{
    item list1[] = {{"egg", 60}, {"butter", 20}, {"rice", 50}, {"oil", 30}};
    item list2[] = {{"butter", 20}, {"egg", 15}, {"wheat", 40}, {"rice", 60}};

    int m = sizeof(list1) / sizeof(list1[0]);
    int n = sizeof(list2) / sizeof(list2[0]);

    cout<< getItemCount(list1, m, list2, n);

    return 0;
}

2

 

Java Code

import java.util.*;

class CountItems
{
    public static class item
    {
        String name;
        int price;
        item(String name, int price)
        {
            this.name=name;
            this.price=price;
        }
    };
    public static int getItemCount(item list1[], int m,item list2[], int n)
    {
        HashMap<String, Integer> MAP=new HashMap<>();
        int output = 0;

        for (int i = 0; i < m; i++)
        {
            MAP.put(list1[i].name, list1[i].price);

        }
        for (int i = 0; i < n; i++)
        {
            if ((MAP.containsKey(list2[i].name) && (MAP.get(list2[i].name) != list2[i].price)))
                output++;
        }
        return output;
    }
    public static void main(String [] args)
    {
        item list1[] = {new item("egg", 60), new item("butter", 20),new item("rice", 50), new item("oil", 30)};

        item list2[] = {new item("butter", 20), new item("egg", 15),new item("wheat", 40), new item("rice", 60)};
        int m = list1.length;
        int n = list2.length;
        System.out.println(getItemCount(list1, m, list2, n));

    }
}

2

Complexity Analysis

Time Complexity for count common items with different prices problem

O(m+n) where “m” and “n” is the number of elements in list1 and list2.

Space Complexity for count common items with different prices problem

Since we are storing the elements only of list 1 in the map, the space complexity is dependent only on the size of list1. Thus space complexity is O(m) where “m” is the number of elements in the list.

Translate »