Sudo Placement | Beautiful Pairs
Given two arrays of integers where maximum size of first array is big and that of second array is small. Your task is to find if there is a pair in the first array whose sum is present in the second array.
Examples:
Input: 4 1 5 10 8 3 2 20 13 Output: 1
Approach: We have x + y = z. This can be rewritten as x = z – y. This means we need to find an element x in array 1 such that it is the result of z(second array) – y(first array). For this, use hashing to keep track of such element x.
Implementation:
C++
// C++ code for finding required pairs #include <bits/stdc++.h> using namespace std; // The function to check if beautiful pair exists bool pairExists( int arr1[], int m, int arr2[], int n) { // Set for hashing unordered_set< int > s; // Traversing the first array for ( int i = 0; i < m; i++) { // Traversing the second array to check for // every j corresponding to single i for ( int j = 0; j < n; j++) { // x + y = z => x = y - z if (s.find(arr2[j] - arr1[i]) != s.end()) // if such x exists then we return true return true ; } // hash to make use of it next time s.insert(arr1[i]); } // no pair exists return false ; } // Driver Code int main() { int arr1[] = { 1, 5, 10, 8 }; int arr2[] = { 2, 20, 13 }; // If pair exists then 1 else 0 // 2nd argument as size of first array // fourth argument as sizeof 2nd array if (pairExists(arr1, 4, arr2, 3)) cout << 1 << endl; else cout << 0 << endl; return 0; } |
Java
// Java code for finding required pairs import java.util.*; class GFG { // The function to check if beautiful pair exists static boolean pairExists( int []arr1, int m, int []arr2, int n) { // Set for hashing Set<Integer> s = new HashSet<Integer>(); // Traversing the first array for ( int i = 0 ; i < m; i++) { // Traversing the second array to check for // every j corresponding to single i for ( int j = 0 ; j < n; j++) { // x + y = z => x = y - z if (s.contains(arr2[j] - arr1[i])) // if such x exists then we return true return true ; } // hash to make use of it next time s.add(arr1[i]); } // no pair exists return false ; } // Driver Code public static void main(String []args) { int []arr1 = { 1 , 5 , 10 , 8 }; int []arr2 = { 2 , 20 , 13 }; // If pair exists then 1 else 0 // 2nd argument as size of first array // fourth argument as sizeof 2nd array if (pairExists(arr1, 4 , arr2, 3 )) System.out.println( 1 ); else System.out.println( 0 ); } // This code is contributed by ihritik } |
Python3
# Python3 code for finding required pairs from typing import List # The function to check if beautiful pair exists def pairExists(arr1: List [ int ], m: int , arr2: List [ int ], n: int ) - > bool : # Set for hashing s = set () # Traversing the first array for i in range (m): # Traversing the second array to check for # every j corresponding to single i for j in range (n): # x + y = z => x = y - z if (arr2[ 2 ] - arr1[ 2 ]) not in s: # If such x exists then we # return true return True # Hash to make use of it next time s.add(arr1[i]) # No pair exists return False # Driver Code if __name__ = = "__main__" : arr1 = [ 1 , 5 , 10 , 8 ] arr2 = [ 2 , 20 , 13 ] # If pair exists then 1 else 0 # 2nd argument as size of first array # fourth argument as sizeof 2nd array if (pairExists(arr1, 4 , arr2, 3 )): print ( 1 ) else : print ( 0 ) # This code is contributed by sanjeev2552 |
C#
// C# code for finding required pairs using System; using System.Collections.Generic; class GFG { // The function to check if // beautiful pair exists static bool pairExists( int []arr1, int m, int []arr2, int n) { // Set for hashing HashSet< int > s = new HashSet< int >(); // Traversing the first array for ( int i = 0; i < m; i++) { // Traversing the second array to check for // every j corresponding to single i for ( int j = 0; j < n; j++) { // x + y = z => x = y - z if (s.Contains(arr2[j] - arr1[i])) // if such x exists then we return true return true ; } // hash to make use of it next time s.Add(arr1[i]); } // no pair exists return false ; } // Driver Code public static void Main() { int []arr1 = { 1, 5, 10, 8 }; int []arr2 = { 2, 20, 13 }; // If pair exists then 1 else 0 // 2nd argument as size of first array // fourth argument as sizeof 2nd array if (pairExists(arr1, 4, arr2, 3)) Console.WriteLine(1); else Console.WriteLine(0); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript code for finding required pairs // The function to check if beautiful pair exists function pairExists(arr1, m, arr2, n) { // Set for hashing let s = new Set(); // Traversing the first array for (let i = 0; i < m; i++) { // Traversing the second array to check for // every j corresponding to single i for (let j = 0; j < n; j++) { // x + y = z => x = y - z if (s.has(arr2[j] - arr1[i])) // if such x exists then we return true return true ; } // hash to make use of it next time s.add(arr1[i]); } // no pair exists return false ; } // Driver Code let arr1 = [1, 5, 10, 8]; let arr2 = [2, 20, 13]; // If pair exists then 1 else 0 // 2nd argument as size of first array // fourth argument as sizeof 2nd array if (pairExists(arr1, 4, arr2, 3)) document.write(1 + "<br>" ); else document.write(0 + "<br>" ); </script> |
Output
1
Time Complexity: O(m*n)
Auxiliary Space: O(m)
Contact Us