Given N pairs of integers, each integer is between 1 to M, the task is to check if there exist two integers x and y such that at least one of the integers is present in each of the pairs.
Examples:
Input: N = 7, M = 6, arr[] = {{5, 6}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}
Output: NO
Explanation: Can’t choose any x, or y because
for each such pair you can find a given pair
where both numbers are different from chosen integers.Input: N = 5, M = 6, {{6, 4}, {2, 3}, {3, 4}, {4, 5}, {5, 6}}
Output: YES
Explanation: Choose x = 5 and y = 3.
Because either x or y is present in all the pairs.
Approach 1: The problem can be solved based on the following idea:
Consider the first pair of the array to be the desired pair (x, y). If there is a pair where none of the elements is present then one from that given pair must be the part of the desired pair.
So now there are total 4 elements which may form the desired pair. Check all possible combinations of pairs and find if any of them is the desired pair.
Follow the steps to solve the problem:
- Create 2 variables (x1, y1) containing each of the array’s first elements.
- Now traverse from i = 0 to N-1:
- Check if none of x1 or y1 is present in the pair.
- If the above condition is true consider the elements to be another pair (x2, y2).
- Now check for all 6 possible combinations of x1, x2, y1, and y2.
- If one of these combinations exists in each given pair then the solution is possible.
- Otherwise, there is no such pair.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check if x or y is present// in each of the given pairsbool check(int x, int y, vector<vector<int>> arr){ for (int i = 0; i < arr.size(); i++) if (x != arr[i][0] && y != arr[i][0] && x != arr[i][1] && y != arr[i][1]) return false; return true;}// Function to find the desired pairstring pairs(int n, vector<vector<int>> arr){ int x1 = arr[0][0]; int y1 = arr[0][1]; int x2 = 0; int y2 = 0; // Finding values which do not contain // the values in 1st array index for (int i = 1; i < n; i++) { if (x1 != arr[i][0] && x1 != arr[i][1] && y1 != arr[i][0] && y1 != arr[i][1]) { x2 = arr[i][0]; y2 = arr[i][1]; } } if (check(x1, x2, arr) || check(x1, y1, arr) || check(x1, y2, arr) || check(x2, y1, arr) || check(x2, y2, arr) || check(y1, y2, arr)) return "Yes"; else return "No";}// Driver codeint main() { int N = 6; int M = 5; vector<vector<int>> arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }; // Function call cout << pairs(N, arr); return 0;}// This code is contributed by Dharanendra L V. |
Java
// Java code to implement the approachclass GFG{ // Function to check if x or y is present // in each of the given pairs static boolean check(int x, int y, int[][] arr) { for (int i = 0; i < arr.length; i++) if (x != arr[i][0] && y != arr[i][0] && x != arr[i][1] && y != arr[i][1]) return false; return true; } // Function to find the desired pair static String pairs(int n, int[][] arr) { int x1 = arr[0][0]; int y1 = arr[0][1]; int x2 = 0; int y2 = 0; // Finding values which do not contain // the values in 1st array index for (int i = 1; i < n; i++) { if (x1 != arr[i][0] && x1 != arr[i][1] && y1 != arr[i][0] && y1 != arr[i][1]) { x2 = arr[i][0]; y2 = arr[i][1]; } } if (check(x1, x2, arr) || check(x1, y1, arr) || check(x1, y2, arr) || check(x2, y1, arr) || check(x2, y2, arr) || check(y1, y2, arr)) return "Yes"; else return "No"; } // Driver code public static void main(String[] args) { int N = 6; int M = 5; int[][] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }; // Function call System.out.println(pairs(N, arr)); }}// This code is contributed by shikhasingrajput |
Python3
# Python 3 code to implement the approach# Function to check if x or y is present# in each of the given pairsdef check(x, y, arr): for i in range(len(arr)): if x != arr[i][0] and y != arr[i][0] \ and x != arr[i][1] and y != arr[i][1]: return False return True# Function to find the desired pairdef pairs(n, arr): x1 = arr[0][0] y1 = arr[0][1] x2 = 0 y2 = 0 # Finding values which do not contain # the values in 1st array index for i in range(1, n): if x1 != arr[i][0] and x1 != arr[i][1] \ and y1 != arr[i][0] and y1 != arr[i][1]: x2 = arr[i][0] y2 = arr[i][1] if check(x1, x2, arr) or check(x1, y1, arr) or \ check(x1, y2, arr) or check(x2, y1, arr) or \ check(x2, y2, arr) or check(y1, y2, arr): return 'YES' else: return 'NO'# Driver codeif __name__ == '__main__': N = 6 M = 5 arr = [[2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]] # Function call print(pairs(N, arr)) |
C#
// C# code to implement the approachusing System;class GFG { // Function to check if x or y is present // in each of the given pairs static bool check(int x, int y, int[, ] arr) { for (int i = 0; i < arr.Length; i++) if (x != arr[i, 0] && y != arr[i, 0] && x != arr[i, 1] && y != arr[i, 1]) return false; return true; } // Function to find the desired pair static string pairs(int n, int[, ] arr) { int x1 = arr[0, 0]; int y1 = arr[0, 1]; int x2 = 0; int y2 = 0; // Finding values which do not contain // the values in 1st array index for (int i = 1; i < n; i++) { if (x1 != arr[i, 0] && x1 != arr[i, 1] && y1 != arr[i, 0] && y1 != arr[i, 1]) { x2 = arr[i, 0]; y2 = arr[i, 1]; } } if (check(x1, x2, arr) || check(x1, y1, arr) || check(x1, y2, arr) || check(x2, y1, arr) || check(x2, y2, arr) || check(y1, y2, arr)) return "Yes"; else return "No"; } // Driver code public static void Main(string[] args) { int N = 6; int M = 5; int[, ] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }; // Function call Console.WriteLine(pairs(N, arr)); }}// This code is contributed by phasing17 |
Javascript
<script> // JavaScript code for the above approach // Function to check if x or y is present // in each of the given pairs function check(x, y, arr) { for (let i = 0; i < arr.length; i++) if (x != arr[i][0] && y != arr[i][0] && x != arr[i][1] && y != arr[i][1]) return false; return true; } // Function to find the desired pair function pairs(n, arr) { let x1 = arr[0][0]; let y1 = arr[0][1]; let x2 = 0; let y2 = 0; // Finding values which do not contain // the values in 1st array index for (let i = 1; i < n; i++) { if (x1 != arr[i][0] && x1 != arr[i][1] && y1 != arr[i][0] && y1 != arr[i][1]) { x2 = arr[i][0]; y2 = arr[i][1]; } } if (check(x1, x2, arr) || check(x1, y1, arr) || check(x1, y2, arr) || check(x2, y1, arr) || check(x2, y2, arr) || check(y1, y2, arr)) return "YES"; else return "NO"; } // Driver Code let N = 6; let M = 5; let arr = [[ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ]]; // Function call document.write(pairs(N, arr)); // This code is contributed by sanjoy_62. </script> |
Output
NO
Time Complexity: O(N).
Auxiliary Space: O(1)
Approach 2: The idea for this approach is also similar to the one mentioned above. The only difference is that:
In the previous case, we were using all the possible combinations. If observed carefully, we can conclude that there must be one value from the pair (x1, y1) and one value from (x2, y2) because if this is not done then one of the pairs will be neglected.
So in this case we will be checking only for 4 possible pairs i.e., (x1, y2), (x1, x2), (y1, y2), and (x2, y1).
Follow the steps mentioned below to implement the idea:
- Consider the first element of the first pair. Let’s say (x1, y1) is pair, then consider x1.
- Find the pair where x1 doesn’t exist.
- Consider that pair as (x2, y2), and take the value x2:
- Check for all the other pairs if (x1, x2) exists in each pair.
- If exits print ‘Yes’, else repeat step 3 with the value y2.
- If pair (x1, y2) exits in each pair print ‘Yes’, else repeat step-1 to step-3 with value y1.
- If after the above operation there still is not any pair, then no such pair is possible.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check if x or y is present in each of the// given pairsbool check(int x, int y, vector<vector<int> >& arr, int n){ // Loop to check if x or y is present in the pairs for (int i = 1; i < n; i++) { if (arr[i][0] == y || arr[i][1] == y || arr[i][0] == x || arr[i][1] == x) { continue; } else { // If x and y are not present in all the // array pairs return true; } } return false;}// Function to find the index of the first pair where x// is not presentint findIndex(int x, vector<vector<int> >& arr, int n){ for (int i = 1; i < n; i++) { if (arr[i][0] != x && arr[i][1] != x) { return i; } } return n;}// Function to find if the required pair is present in// array or not.string find(vector<vector<int> > a, int n){ int x = a[0][0]; int k = findIndex(x, a, n); // Taking the first value of kth index if (k >= n) { return "YES"; } int y = a[k][0]; int flag = 0; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Considering second value of kth index y = a[k][1]; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Second element is in 1st index x = a[0][1]; k = findIndex(x, a, n); if (k >= n) { return "YES"; } // Taking the first value of kth index y = a[k][0]; if (check(x, y, a, n)) { // Considering second value of kth index y = a[k][1]; if (check(x, y, a, n)) { return "NO"; } } } } return "YES";}int main(){ int N = 6; int M = 5; vector<vector<int> > arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }; // Function call cout << find(arr, N); return 0;} // This code is contributed by rakeshsahni |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to check if x or y is present in each of the // given pairs public static boolean check(int x, int y, int[][] arr, int n) { // Loop to check if x or y is present in the pairs for (int i = 1; i < n; i++) { if (arr[i][0] == y || arr[i][1] == y || arr[i][0] == x || arr[i][1] == x) { continue; } else { // If x and y are not present in all the // array pairs return true; } } return false; } // Function to find the index of the first pair where x // is not present public static int findIndex(int x, int[][] arr, int n) { for (int i = 1; i < n; i++) { if (arr[i][0] != x && arr[i][1] != x) { return i; } } return n; } // Function to find if the required pair is present in // array or not. public static String find(int[][] a, int n) { int x = a[0][0]; int k = findIndex(x, a, n); // Taking the first value of kth index if (k >= n) { return "YES"; } int y = a[k][0]; int flag = 0; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Considering second value of kth index y = a[k][1]; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Second element is in 1st index x = a[0][1]; k = findIndex(x, a, n); if (k >= n) { return "YES"; } // Taking the first value of kth index y = a[k][0]; if (check(x, y, a, n)) { // Considering second value of kth index y = a[k][1]; if (check(x, y, a, n)) { return "NO"; } } } } return "YES"; } public static void main(String[] args) { int N = 6; int M = 5; int[][] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }; // Function call System.out.print(find(arr, N)); }}// This code is contributed by lokesh (lokeshmvs21). |
Python3
# Python 3 code to implement the approach# Function to check if x or y is present# in each of the given pairsdef check(x, y, arr, n): # Loop to check if x or y is present in the pairs for i in range(1, n): if arr[i][0] == y or arr[i][1] == y \ or arr[i][0] == x or arr[i][1] == x: continue else: # If x and y are not present # in all the array pairs return True return False# Function to find the index of the# first pair where x is not presentdef findIndex(x, arr, n): for i in range(1, n): if arr[i][0] != x and arr[i][1] != x: return i return n# Function to find if the# required pair is present in array or notdef find(a, n): x = a[0][0] k = findIndex(x, a, n) # Taking the first value of kth index if k >= n: return 'YES' y = a[k][0] flag = 0 # If x and y are not in all array pairs if check(x, y, a, n): # Considering second value of kth index y = a[k][1] # If x and y are not in all array pairs if check(x, y, a, n): # Second element in 1st index x = a[0][1] k = findIndex(x, a, n) if k >= n: return 'YES' # Taking the first value of kth index y = a[k][0] if check(x, y, a, n): # Considering second value of kth index y = a[k][1] if check(x, y, a, n): return 'NO' return 'YES'# Driver codeif __name__ == '__main__': N = 6 M = 5 arr = [[2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]] # Function call print(find(arr, N)) |
C#
// C# program for above approachusing System;class GFG{ // Function to check if x or y is present in each of the // given pairs public static bool check(int x, int y, int[,] arr, int n) { // Loop to check if x or y is present in the pairs for (int i = 1; i < n; i++) { if (arr[i,0] == y || arr[i,1] == y || arr[i,0] == x || arr[i,1] == x) { continue; } else { // If x and y are not present in all the // array pairs return true; } } return false; } // Function to find the index of the first pair where x // is not present public static int findIndex(int x, int[,] arr, int n) { for (int i = 1; i < n; i++) { if (arr[i,0] != x && arr[i,1] != x) { return i; } } return n; } // Function to find if the required pair is present in // array or not. public static String find(int[,] a, int n) { int x = a[0,0]; int k = findIndex(x, a, n); // Taking the first value of kth index if (k >= n) { return "YES"; } int y = a[k,0]; int flag = 0; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Considering second value of kth index y = a[k, 1]; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Second element is in 1st index x = a[0,1]; k = findIndex(x, a, n); if (k >= n) { return "YES"; } // Taking the first value of kth index y = a[k,0]; if (check(x, y, a, n)) { // Considering second value of kth index y = a[k,1]; if (check(x, y, a, n)) { return "NO"; } } } } return "YES"; } // Driver Code public static void Main() { int N = 6; int M = 5; int[,] arr = { { 2, 3 }, { 2, 4 }, { 2, 5 }, { 3, 4 }, { 3, 5 }, { 4, 5 } }; // Function call Console.Write(find(arr, N)); }}// This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for above approach // Function to check if x or y is present in each of the // given pairs function check(x, y, arr, n) { // Loop to check if x or y is present in the pairs for (let i = 1; i < n; i++) { if (arr[i][0] == y || arr[i][1] == y || arr[i][0] == x || arr[i][1] == x) { continue; } else { // If x and y are not present in all the // array pairs return true; } } return false; } // Function to find the index of the first pair where x // is not present function findIndex(x, arr, n) { for (let i = 1; i < n; i++) { if (arr[i][0] != x && arr[i][1] != x) { return i; } } return n; } // Function to find if the required pair is present in // array or not. function find(a, n) { let x = a[0][0]; let k = findIndex(x, a, n); // Taking the first value of kth index if (k >= n) { return "YES"; } let y = a[k][0]; let flag = 0; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Considering second value of kth index y = a[k][1]; // If x and y are not in all array pairs if (check(x, y, a, n)) { // Second element is in 1st index x = a[0][1]; k = findIndex(x, a, n); if (k >= n) { return "YES"; } // Taking the first value of kth index y = a[k][0]; if (check(x, y, a, n)) { // Considering second value of kth index y = a[k][1]; if (check(x, y, a, n)) { return "NO"; } } } } return "YES"; }// Driver Code let N = 6; let M = 5; let arr = [[ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ]]; // Function call document.write(find(arr, N));// This code is contributed by code_hunt.</script> |
Output
NO
Time Complexity: O(N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
