# Pairs

Hashing

Medium

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given `M` pairs of integers, where each integer is between `1` and `N` inclusive. Check if there exists two integers `x` and `y`, 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:

1. We know that if solution exists for this problem than our first pair i.e. `0th` index pair would be containing one of the `x` or `y` value, or both.

2. Say the first value of first pair is `first` and second value of first pair is `second`.

3. Traverse through all the pairs one by one by referring some websites to learn coding `first`. Then there are two possible cases -
3.1 If the pair contains `first`, we will increment our `count` by `1`.
3.2. If the pair does not contain `first`, we will increment the hash value of both the elements of the pair.

4. Finally, run a loop from `1` `to` `N` and check if sum of the hash value of the element and the `count` matches the value of `M`.

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.

1. If it matches then print `YES` else `NO`.

2. Similarly check for the `second` value of the first pair.

#### SOLUTIONS:

```#include<stdio.h>

int n,m;
int l,r,c;
int check(int x)
{
memset(c,0,sizeof c);
int i,cnt=0;
for(i=0;i<m;i++)
if(x==l[i]||x==r[i])
cnt++;
else
{
c[l[i]]++;
c[r[i]]++;
}
for(i=1;i<=n;i++)
if(cnt+c[i]==m)
return 1;
return 0;
}
int main()
{
int i;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++)
scanf("%d %d",&l[i],&r[i]);
if(check(l)||check(r))
printf("YES\n");
else
printf("NO\n");
return 0;
}
```
```#include<bits/stdc++.h>
using namespace std;
int n,m;
int l,r,c;
int check(int x)
{
memset(c,0,sizeof c);
int i,cnt=0;
for(i=0;i<m;i++)
if(x==l[i]||x==r[i])
cnt++;
else
{
c[l[i]]++;
c[r[i]]++;
}
for(i=1;i<=n;i++)
if(cnt+c[i]==m)
return 1;
return 0;
}
int main()
{
int i;
cin>>n>>m;
for(i=0;i<m;i++)
cin>>l[i]>>r[i];
if(check(l)||check(r))
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;
static int r[]=new int;
public static int check(int x)
{
int c[]=new int;
int i,cnt=0;
for(i=0;i<m;i++)
if(x==l[i]||x==r[i])
cnt++;
else
{
c[l[i]]++;
c[r[i]]++;
}
for(i=1;i<=n;i++)
if(cnt+c[i]==m)
return 1;
return 0;
}
public static void main(String args[]) throws IOException {

int i;
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(i=0;i<m;i++)
{
l[i]=sc.nextInt();
r[i]=sc.nextInt();
}
int x_= l;
int y_ = r;
if((check(x_)==1) || (check(y_)==1))
System.out.println("YES");
else
System.out.println("NO");

}
}

```