Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Pairs

Last Updated on March 31, 2022 by Ria Pathak

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 and check if it contains the value of `first`. Then there are two possible cases –

• If the pair contains `first`, we will increment our `count` by `1`.
• 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

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
```
```#include
using 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.