Dadas dos listas list1 y list2 que contienen m y n elementos respectivamente. Cada artículo está asociado a dos campos: nombre y precio. El problema es contar artículos que están en ambas listas pero con precios diferentes.
Ejemplos:
Input : list1[] = {{"apple", 60}, {"bread", 20},
{"wheat", 50}, {"oil", 30}}
list2[] = {{"milk", 20}, {"bread", 15},
{"wheat", 40}, {"apple", 60}}
Output : 2
bread and wheat are the two items common to both the
lists but with different prices.
Fuente: Experiencia de entrevistas de Cognizant | conjunto 5
Método 1 (enfoque ingenuo): usando dos bucles anidados, compare cada elemento de list1 con todos los elementos de list2 . Si se encuentra una coincidencia con un precio diferente, aumente el conteo .
C++
// C++ implementation to count items common to both
// the lists but with different prices
#include <bits/stdc++.h>
using namespace std;
// details of an item
struct item
{
string name;
int price;
};
// function to count items common to both
// the lists but with different prices
int countItems(item list1[], int m,
item list2[], int n)
{
int count = 0;
// for each item of 'list1' check if it is in 'list2'
// but with a different price
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if ((list1[i].name.compare(list2[j].name) == 0) &&
(list1[i].price != list2[j].price))
count++;
// required count of items
return count;
}
// Driver program to test above
int main()
{
item list1[] = {{"apple", 60}, {"bread", 20},
{"wheat", 50}, {"oil", 30}};
item list2[] = {{"milk", 20}, {"bread", 15},
{"wheat", 40}, {"apple", 60}};
int m = sizeof(list1) / sizeof(list1[0]);
int n = sizeof(list2) / sizeof(list2[0]);
cout << "Count = "
<< countItems(list1, m, list2, n);
return 0;
}
Java
// Java implementation to count items common to both
// the lists but with different prices
class GFG{
// details of an item
static class item
{
String name;
int price;
public item(String name, int price) {
this.name = name;
this.price = price;
}
};
// function to count items common to both
// the lists but with different prices
static int countItems(item list1[], int m,
item list2[], int n)
{
int count = 0;
// for each item of 'list1' check if it is in 'list2'
// but with a different price
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if ((list1[i].name.compareTo(list2[j].name) == 0) &&
(list1[i].price != list2[j].price))
count++;
// required count of items
return count;
}
// Driver code
public static void main(String[] args)
{
item list1[] = {new item("apple", 60), new item("bread", 20),
new item("wheat", 50), new item("oil", 30)};
item list2[] = {new item("milk", 20), new item("bread", 15),
new item("wheat", 40), new item("apple", 60)};
int m = list1.length;
int n = list2.length;
System.out.print("Count = "
+ countItems(list1, m, list2, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python implementation to
# count items common to both
# the lists but with different
# prices
# function to count items
# common to both
# the lists but with different prices
def countItems(list1, list2):
count = 0
# for each item of 'list1'
# check if it is in 'list2'
# but with a different price
for i in list1:
for j in list2:
if i[0] == j[0] and i[1] != j[1]:
count += 1
# required count of items
return count
# Driver program to test above
list1 = [("apple", 60), ("bread", 20),
("wheat", 50), ("oil", 30)]
list2 = [("milk", 20), ("bread", 15),
("wheat", 40), ("apple", 60)]
print("Count = ", countItems(list1, list2))
# This code is contributed by Ansu Kumari.
C#
// C# implementation to count items common to both
// the lists but with different prices
using System;
class GFG{
// details of an item
class item
{
public String name;
public int price;
public item(String name, int price) {
this.name = name;
this.price = price;
}
};
// function to count items common to both
// the lists but with different prices
static int countItems(item []list1, int m,
item []list2, int n)
{
int count = 0;
// for each item of 'list1' check if it is in 'list2'
// but with a different price
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if ((list1[i].name.CompareTo(list2[j].name) == 0) &&
(list1[i].price != list2[j].price))
count++;
// required count of items
return count;
}
// Driver code
public static void Main(String[] args)
{
item []list1 = {new item("apple", 60), new item("bread", 20),
new item("wheat", 50), new item("oil", 30)};
item []list2 = {new item("milk", 20), new item("bread", 15),
new item("wheat", 40), new item("apple", 60)};
int m = list1.Length;
int n = list2.Length;
Console.Write("Count = "
+ countItems(list1, m, list2, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation to
// count items common to both
// the lists but with different prices
// function to count items common to both
// the lists but with different prices
function countItems(list1, m, list2, n)
{
var count = 0;
// for each item of 'list1'
// check if it is in 'list2'
// but with a different price
for (var i = 0; i < m; i++)
for (var j = 0; j < n; j++)
if (list1[i][0] === list2[j][0] &&
(list1[i][1] != list2[j][1]))
count++;
// required count of items
return count;
}
// Driver program to test above
var list1 = [["apple", 60], ["bread", 20],
["wheat", 50], ["oil", 30]];
var list2 = [["milk", 20], ["bread", 15],
["wheat", 40], ["apple", 60]];
var m = list1.length;
var n = list2.length;
document.write( "Count = " + countItems(list1, m, list2, n));
</script>
Producción:
Count = 2
Complejidad temporal: O(m*n).
Espacio Auxiliar: O(1).
Método 2 (búsqueda binaria): ordene la lista 2 en orden alfabético según el nombre de sus elementos. Ahora, para cada elemento de la lista1 , verifique si está presente en la lista2 utilizando la técnica de búsqueda binaria y obtenga su precio de la lista2 . Si los precios son diferentes entonces incremente el conteo .
C++
// C++ implementation to count
// items common to both the lists
// but with different prices
#include <bits/stdc++.h>
using namespace std;
// Details of an item
struct item
{
string name;
int price;
};
// comparator function
// used for sorting
bool compare(struct item a,
struct item b)
{
return (a.name.compare
(b.name) <= 0);
}
// Function to search 'str'
// in 'list2[]'. If it exists then
// price associated with 'str'
// in 'list2[]' is being returned
// else -1 is returned. Here binary
// search technique is being applied
// for searching
int binary_search(item list2[], int low,
int high, string str)
{
while (low <= high)
{
int mid = (low + high) / 2;
// if true the item 'str'
// is in 'list2'
if (list2[mid].name.compare(str) == 0)
return list2[mid].price;
else if (list2[mid].name.compare(str) < 0)
low = mid + 1;
else
high = mid - 1;
}
// item 'str' is not in 'list2'
return -1;
}
// Function to count items common to both
// the lists but with different prices
int countItems(item list1[], int m,
item list2[], int n)
{
// sort 'list2' in alphabetical
// order of items name
sort(list2, list2 + n,
compare);
// initial count
int count = 0;
for (int i = 0; i < m; i++)
{
// get the price of item 'list1[i]'
// from 'list2' if item in not
// present in second list then
// -1 is being obtained
int r = binary_search(list2, 0, n - 1,
list1[i].name);
// if item is present in list2
// with a different price
if ((r != -1) &&
(r != list1[i].price))
count++;
}
// Required count of items
return count;
}
// Driver code
int main()
{
item list1[] = {{"apple", 60},
{"bread", 20},
{"wheat", 50},
{"oil", 30}};
item list2[] = {{"milk", 20},
{"bread", 15},
{"wheat", 40},
{"apple", 60}};
int m = sizeof(list1) /
sizeof(list1[0]);
int n = sizeof(list2) /
sizeof(list2[0]);
cout << "Count = " <<
countItems(list1, m,
list2, n);
return 0;
}
Java
// Java implementation to count
// items common to both the lists
// but with different prices
import java.util.*;
class GFG{
// Details of an item
static class item
{
String name;
int price;
item(String name,
int price)
{
this.name = name;
this.price = price;
}
};
// comparator function used for sorting
static class Com implements Comparator<item>
{
public int compare(item a,
item b)
{
return a.name.compareTo(b.name);
}
}
// Function to search 'str' in 'list2[]'.
// If it exists then price associated
// with 'str' in 'list2[]' is being
// returned else -1 is returned. Here
// binary search technique is being
// applied for searching
static int binary_search(item list2[],
int low, int high,
String str)
{
while (low <= high)
{
int mid = (low + high) / 2;
// if true the item 'str' is in 'list2'
if (list2[mid].name.compareTo(str) == 0)
return list2[mid].price;
else if (list2[mid].name.compareTo(str) < 0)
low = mid + 1;
else
high = mid - 1;
}
// item 'str' is not
// in 'list2'
return -1;
}
// Function to count items common to both
// the lists but with different prices
static int countItems(item list1[], int m,
item list2[], int n)
{
// sort 'list2' in alphabetical
// order of items name
Arrays.sort(list2, new Com());
// initial count
int count = 0;
for (int i = 0; i < m; i++)
{
// get the price of item 'list1[i]'
// from 'list2' if item in not
// present in second list then -1
// is being obtained
int r = binary_search(list2, 0,
n - 1,
list1[i].name);
// if item is present in list2
// with a different price
if ((r != -1) &&
(r != list1[i].price))
count++;
}
// Required count of items
return count;
}
// Driver code
public static void main(String[] args)
{
item[] list1 = {new item("apple", 60),
new item("bread", 20),
new item("wheat", 50),
new item("oil", 30)};
item list2[] = {new item("milk", 20),
new item("bread", 15),
new item("wheat", 40),
new item("apple", 60)};
int m = list1.length;
int n = list2.length;
System.out.print("Count = " +
countItems(list1, m,
list2, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to count
# items common to both the lists
# but with different prices
# Details of an item
from ast import Str
from functools import cmp_to_key
class item:
def __init__(self, name, price):
self.name = name
self.price = price
# Function to search 'str' in 'list2[]'.
# If it exists then price associated
# with 'str' in 'list2[]' is being
# returned else -1 is returned. Here
# binary search technique is being
# applied for searching
def binary_search(list2, low, high, str):
while (low <= high):
mid = ((low + high) // 2)
# if true the item 'str' is in 'list2'
# print(list2[mid].name,str)
if (list2[mid].name == str):
return list2[mid].price
elif (list2[mid].name < str):
low = mid + 1
else:
high = mid - 1
# item 'str' is not
# in 'list2'
return -1
# Function to count items common to both
# the lists but with different prices
def custom_logic(a, b):
return a.name == b.name
def countItems(list1, m, list2, n):
# sort 'list2' in alphabetical
# order of items name
sorted(list2,key=cmp_to_key(custom_logic))
# initial count
count = 0
for i in range(m):
# get the price of item 'list1[i]'
# from 'list2' if item in not
# present in second list then -1
# is being obtained
r = binary_search(list2, 0,
n - 1,
list1[i].name)
# if item is present in list2
# with a different price
if ((r != -1) and (r != list1[i].price)):
count += 1
# Required count of items
return count
# Driver code
list1=[item("apple", 60),
item("bread", 20),
item("wheat", 50),
item("oil", 30)]
list2=[item("milk", 20),
item("bread", 15),
item("wheat", 40),
item("apple", 60)]
m = len(list1)
n = len(list2)
print(f"Count = {countItems(list1, m,list2, n)}")
# This code is contributed by shinjanpatra
Javascript
<script>
// Javascript implementation to count
// items common to both the lists
// but with different prices
// Details of an item
class item
{
constructor(name,price)
{
this.name = name;
this.price = price;
}
}
// Function to search 'str' in 'list2[]'.
// If it exists then price associated
// with 'str' in 'list2[]' is being
// returned else -1 is returned. Here
// binary search technique is being
// applied for searching
function binary_search(list2,low,high,str)
{
while (low <= high)
{
let mid = Math.floor((low + high) / 2);
// if true the item 'str' is in 'list2'
if (list2[mid].name == (str))
return list2[mid].price;
else if (list2[mid].name < (str))
low = mid + 1;
else
high = mid - 1;
}
// item 'str' is not
// in 'list2'
return -1;
}
// Function to count items common to both
// the lists but with different prices
function countItems(list1, m, list2, n)
{
// sort 'list2' in alphabetical
// order of items name
list2.sort(function(a,b){return a.name==b.name;});
// initial count
let count = 0;
for (let i = 0; i < m; i++)
{
// get the price of item 'list1[i]'
// from 'list2' if item in not
// present in second list then -1
// is being obtained
let r = binary_search(list2, 0,
n - 1,
list1[i].name);
// if item is present in list2
// with a different price
if ((r != -1) &&
(r != list1[i].price))
count++;
}
// Required count of items
return count;
}
// Driver code
let list1=[new item("apple", 60),
new item("bread", 20),
new item("wheat", 50),
new item("oil", 30)];
let list2=[new item("milk", 20),
new item("bread", 15),
new item("wheat", 40),
new item("apple", 60)];
let m = list1.length;
let n = list2.length;
document.write("Count = " +
countItems(list1, m,
list2, n));
// This code is contributed by patel2127
</script>
Producción:
Count = 2
Tiempo Complejidad: (m*log 2 n).
Espacio Auxiliar: O(1).
Para mayor eficiencia, la lista con el número máximo de elementos debe ordenarse y usarse para la búsqueda binaria.
Método 3 (Enfoque eficiente): Cree una tabla hash con (clave, valor) tupla como (nombre del artículo, precio) . Inserte los elementos de list1 en la tabla hash. Ahora, para cada elemento de list2 , verifique si es la tabla hash o no. Si está presente, compruebe si su precio es diferente del valor de la tabla hash. Si es así, aumente el conteo .
C++
// C++ implementation to count items common to both
// the lists but with different prices
#include <bits/stdc++.h>
using namespace std;
// details of an item
struct item
{
string name;
int price;
};
// function to count items common to both
// the lists but with different prices
int countItems(item list1[], int m,
item list2[], int n)
{
// 'um' implemented as hash table that contains
// item name as the key and price as the value
// associated with the key
unordered_map<string, int> um;
int count = 0;
// insert elements of 'list1' in 'um'
for (int i = 0; i < m; i++)
um[list1[i].name] = list1[i].price;
// for each element of 'list2' check if it is
// present in 'um' with a different price
// value
for (int i = 0; i < n; i++)
if ((um.find(list2[i].name) != um.end()) &&
(um[list2[i].name] != list2[i].price))
count++;
// required count of items
return count;
}
// Driver program to test above
int main()
{
item list1[] = {{"apple", 60}, {"bread", 20},
{"wheat", 50}, {"oil", 30}};
item list2[] = {{"milk", 20}, {"bread", 15},
{"wheat", 40}, {"apple", 60}};
int m = sizeof(list1) / sizeof(list1[0]);
int n = sizeof(list2) / sizeof(list2[0]);
cout << "Count = "
<< countItems(list1, m, list2, n);
return 0;
}
Java
// Java implementation to count
// items common to both the lists
// but with different prices
import java.util.*;
class GFG {
// details of an item
static class item {
String name;
int price;
public item(String name, int price)
{
this.name = name;
this.price = price;
}
};
// function to count items common to both
// the lists but with different prices
static int countItems(item list1[], int m, item list2[],
int n)
{
// 'um' implemented as hash table that contains
// item name as the key and price as the value
// associated with the key
HashMap<String, Integer> um = new HashMap<>();
int count = 0;
// insert elements of 'list1' in 'um'
for (int i = 0; i < m; i++)
um.put(list1[i].name, list1[i].price);
// for each element of 'list2' check if it is
// present in 'um' with a different price
// value
for (int i = 0; i < n; i++)
if ((um.containsKey(list2[i].name))
&& (um.get(list2[i].name)
!= list2[i].price))
count++;
// required count of items
return count;
}
// Driver program to test above
public static void main(String[] args)
{
item list1[] = { new item("apple", 60),
new item("bread", 20),
new item("wheat", 50),
new item("oil", 30) };
item list2[]
= { new item("milk", 20), new item("bread", 15),
new item("wheat", 40),
new item("apple", 60) };
int m = list1.length;
int n = list2.length;
System.out.print("Count = "
+ countItems(list1, m, list2, n));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation to count items common to both
# the lists but with different prices
# details of an item
class item:
def __init__(self, name, price):
self.name = name
self.price = price
# function to count items common to both
# the lists but with different prices
def countItems(list1, m,list2, n):
# 'um' implemented as hash table that contains
# item name as the key and price as the value
# associated with the key
um = {}
count = 0
# insert elements of 'list1' in 'um'
for i in range(m):
um[list1[i].name] = list1[i].price;
# for each element of 'list2' check if it is
# present in 'um' with a different price
# value
for i in range(n):
if ((um.get(list2[i].name) != None) and (um[list2[i].name] != list2[i].price)):
count+=1
# required count of items
return count
# Driver program to test above
list1=[item("apple", 60),
item("bread", 20),
item("wheat", 50),
item("oil", 30)]
list2=[item("milk", 20),
item("bread", 15),
item("wheat", 40),
item("apple", 60)]
m = len(list1)
n = len(list2)
print("Count = " ,countItems(list1, m, list2, n))
# This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# implementation to count
// items common to both the lists
// but with different prices
using System;
using System.Collections.Generic;
class GFG{
// Details of an item
public class item
{
public String name;
public int price;
public item(String name,
int price)
{
this.name = name;
this.price = price;
}
};
// Function to count items common to
// both the lists but with different prices
static int countItems(item []list1, int m,
item []list2, int n)
{
// 'um' implemented as hash table
// that contains item name as the
// key and price as the value
// associated with the key
Dictionary<String,
int> um = new Dictionary<String,
int>();
int count = 0;
// Insert elements of 'list1'
// in 'um'
for (int i = 0; i < m; i++)
um.Add(list1[i].name,
list1[i].price);
// For each element of 'list2'
// check if it is present in
// 'um' with a different price
// value
for (int i = 0; i < n; i++)
if ((um.ContainsKey(list2[i].name)) &&
(um[list2[i].name] != list2[i].price))
count++;
// Required count of items
return count;
}
// Driver code
public static void Main(String[] args)
{
item []list1 = {new item("apple", 60),
new item("bread", 20),
new item("wheat", 50),
new item("oil", 30)};
item []list2 = {new item("milk", 20),
new item("bread", 15),
new item("wheat", 40),
new item("apple", 60)};
int m = list1.Length;
int n = list2.Length;
Console.Write("Count = " +
countItems(list1, m,
list2, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript implementation to count
// items common to both the lists
// but with different prices
// details of an item
class item
{
constructor(name,price)
{
this.name = name;
this.price = price;
}
}
// function to count items common to both
// the lists but with different prices
function countItems(list1,m,list2,n)
{
// 'um' implemented as hash table that contains
// item name as the key and price as the value
// associated with the key
let um = new Map();
let count = 0;
// insert elements of 'list1' in 'um'
for (let i = 0; i < m; i++)
um.set(list1[i].name, list1[i].price);
// for each element of 'list2' check if it is
// present in 'um' with a different price
// value
for (let i = 0; i < n; i++)
if ((um.has(list2[i].name)) &&
(um.get(list2[i].name) != list2[i].price))
count++;
// required count of items
return count;
}
// Driver program to test above
let list1=[new item("apple", 60),
new item("bread", 20),
new item("wheat", 50),
new item("oil", 30)];
let list2=[new item("milk", 20),
new item("bread", 15),
new item("wheat", 40),
new item("apple", 60)];
let m = list1.length;
let n = list2.length;
document.write("Count = " +
countItems(list1, m,
list2, n));
// This code is contributed by unknown2108
</script>
Producción:
Count = 2
Complejidad Temporal: O(m + n).
Espacio Auxiliar: O(m).
Para mayor eficiencia, la lista que tiene un número mínimo de elementos debe insertarse en la tabla hash.
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA