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. 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[300001],r[300001],c[300001];
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[0])||check(r[0]))
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}
#include<bits/stdc++.h>
    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<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[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<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[0];
        int y_ = r[0];
        if((check(x_)==1) || (check(y_)==1))
            System.out.println("YES");
        else
            System.out.println("NO");

  }
}

Space Complexity: O(N), due to an extra array for Hashing.
Previous post Arrange Ways
Next post Minimum characters required to add to given string to make it palindrome

Leave a Reply

Your email address will not be published. Required fields are marked *