Last Updated on March 31, 2022 by Ria Pathak
CONCEPTS USED:
Hashing
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(
SIMPLIFIED)
:
Given
M
pairs of integers, where each integer is between1
andN
inclusive. Check if there exists two integersx
andy
, such that at least of them is present in every pair.
See original problem statement here
For Example:
Input 1: N = 6 , M = 4 and given pairs,
(2, 3)
(3, 4)
(4, 5)
(5, 6)
Output: YES
Explanation : 5 and 3 are the elements such that at least one of them is always present in all the pairs
Input 2: N = 5 , M = 6 and given pairs,
(2, 3)
(2, 4)
(2, 5)
(3, 4)
(3, 5)
(4, 5)
Output: NO
Explanation : There are no two elements such that at least one of them is present in each of the pair.
If we choose 2 and 3, 6th pair does not contain any one of them
If we choose 2 and 4, 5th pair does not contain any one of them
If we choose 2 and 5, 4th pair does not contain any one of them
If we choose 3 and 4, 3rd pair does not contain any one of them
If we choose 3 and 5, 2nd pair does not contain any one of them
If we choose 4 and 5, 1st pair does not contain any one of them
SOLVING APPROACH:

We know that if solution exists for this problem than our first pair i.e. 0^{th} index pair would be containing one of the
x
ory
value, or both. 
Say the first value of first pair is
first
and second value of first pair issecond
. 
Traverse through all the pairs one by one and check if it contains the value of
first
. Then there are two possible cases – If the pair contains
first
, we will increment ourcount
by1
.  If the pair does not contain
first
, we will increment the hash value of both the elements of the pair.
 If the pair contains

Finally, run a loop from
1
to
N
and check if sum of the hash value of the element and thecount
matches the value ofM
.
Reason : It is so because whenever we had first
in a pair we have incremented the value of count
and whenever we didn’t, we had incremented the hash value of current pair of elements. So if the sum of hash value of an element
and count
give us the value of M
, this implies that first
and the element
are those integers out of which at least one of them is present in each and every pair.

If it matches then print
YES
elseNO
. 
Similarly check for the
second
value of the first pair.
SOLUTIONS:
#includeint n,m; int l[300001],r[300001],c[300001]; int check(int x) { memset(c,0,sizeof c); int i,cnt=0; for(i=0;i
#includeusing namespace std; int n,m; int l[300001],r[300001],c[300001]; int check(int x) { memset(c,0,sizeof c); int i,cnt=0; for(i=0;i >n>>m; for(i=0;i >l[i]>>r[i]; if(check(l[0])check(r[0])) cout<<"YES\n"; else cout<<"NO\n"; }
import java.util.*; import java.io.*; public class Main { static int n,m; static int l[]=new int[300001]; static int r[]=new int[300001]; public static int check(int x) { int c[]=new int[300001]; int i,cnt=0; for(i=0;i
n, m = map(int,input().split()) l, r, c = [0 for _ in range(300001)], [0 for _ in range(300001)], [0 for _ in range(300001)] def check(x): cnt = 0 for i in range(m): if x == l[i] or x == r[i]: cnt += 1 else: c[l[i]] += 1 c[r[i]] += 1 for i in range(1, n + 1): if cnt + c[i] == m: return 1 return 0 for i in range(m): arr = list(map(int,input().split())) l[i] = (arr[0]) r[i] = (arr[1]) if check(l[0]) or check(r[0]): print("YES") else: print("NO")
Space Complexity:
O(N)
, due to an extra array for Hashing
.
[forminator_quiz id="690"]
This article tried to discuss the concept of Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing you can check out MYCODE  Competitive Programming.