Pairs

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 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. 0^th 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.

5. If it matches then print YES else NO.

6. 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")

[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.