Count items common to both the lists but with different prices | C ++ implementation to count items common to both the lists but with different prices ; Details of an item ; comparator function used for sorting ; 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 serach technique is being applied for searching ; if true the item ' str ' is in ' list2' ; item ' str ' is not in ' list2' ; Function to count items common to both the lists but with different prices ; sort ' list2' in alphabetcal order of items name ; initial count ; get the price of item ' list1 [ i ] ' from ' list2' if item in not present in second list then - 1 is being obtained ; if item is present in list2 with a different price ; Required count of items ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct item { string name ; int price ; } ; bool compare ( struct item a , struct item b ) { return ( a . name . compare ( b . name ) <= 0 ) ; } int binary_search ( item list2 [ ] , int low , int high , string str ) { while ( low <= high ) { int mid = ( low + high ) / 2 ; 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 ; } return -1 ; } int countItems ( item list1 [ ] , int m , item list2 [ ] , int n ) { sort ( list2 , list2 + n , compare ) ; int count = 0 ; for ( int i = 0 ; i < m ; i ++ ) { int r = binary_search ( list2 , 0 , n - 1 , list1 [ i ] . name ) ; if ( ( r != -1 ) && ( r != list1 [ i ] . price ) ) count ++ ; } return count ; } 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 ; }