Given two arrays arr1[] and arr2[] of size N each and an array Q[][2] consisting of M queries of the form [x, y], the task for each query is to check if the set of values contained from first x elements of arr1[] is equal to set of values from in first y elements of arr2[].
Note: Two sets are equal when they have all their distinct elements equal. For example, {1, 2, 2, } and {1, 2} are equal sets but {1, 2, 3} and {1, 3} are not.
Examples:
Input: arr1[] = {5, 6, 7, 8, 9}, arr2[] = {5, 6, 6, 8, 7}, Q[][] = {{4, 5}, {3, 3}, {2, 3}}
Output:
YES
NO
YES
Explanation:
Query 1: [4, 5] first 4 elements of arr1[] are A = {5, 6, 7, 8} and the first 5 elements of arr2[] are B = {5, 6, 6, 8, 7} since the distinct elements in both of the sets A and B are equal. Hence print “YES“.
Query 2: [3, 3] first 3 elements of arr1[] are A = {5, 6, 7} and the first 3 elements of arr2[] are B = {5, 6, 6} since the distinct elements in both of the sets A and B are not equal. Hence print “NO“.
Query 3: [2, 3] first 2 elements of arr1[] are A = {5, 6} and the first 3 elements of arr2[] are B = {5, 6, 6} since the distinct elements in both of the sets A and B are equal. Hence print “YES”.Input: arr1[] = {1, 2, 2, 3}, arr2[] = {1, 3, 2, 2}, Q[][] = {{2, 2}, {4, 3}, {4, 4}}
Output:
NO
YES
YES
Naive approach: The basic way to solve the problem is as follows:
For each query, we will maintain two sets and we will traverse and insert the first x elements of arr1[] and the first y elements of arr2[]. Then equate these sets and check if they are equal.
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 set of values of the// first X elements are equal to set of// values of first Y elements.void checkEquality(int arr1[], int arr2[], int N, int Q[][2], int M){ // Iterating for each query M for (int i = 0; i < M; i++) { // Query in the form [X, Y] int X = Q[i][0], Y = Q[i][1]; // Declaration of empty sets set<int> s1, s2; // Insert first X elements into set s1 for (int j = 0; j < X; j++) { s1.insert(arr1[j]); } // Insert first Y elements into set s2 for (int j = 0; j < Y; j++) { s2.insert(arr2[j]); } // If both sets are equal if (s1 == s2) { cout << "YES" << endl; } else { cout << "NO" << endl; } }}// Driver Codeint main(){ int arr1[] = { 5, 6, 7, 8, 9 }; int arr2[] = { 5, 6, 6, 8, 7 }; int Q[][2] = { { 4, 5 }, { 3, 3 }, { 2, 3 } }; int N = sizeof(arr1) / sizeof(arr1[0]); int M = sizeof(Q) / sizeof(Q[0]); // Function Call checkEquality(arr1, arr2, N, Q, M); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to check if set of values of the // first X elements are equal to set of // values of first Y elements. static void checkEquality(int[] arr1, int[] arr2, int N, int[][] Q, int M) { // Iterating for each query M for (int i = 0; i < M; i++) { // Query in the form [X, Y] int X = Q[i][0], Y = Q[i][1]; // Declaration of empty sets Set<Integer> s1 = new HashSet<>(); Set<Integer> s2 = new HashSet<>(); // Insert first X elements into set s1 for (int j = 0; j < X; j++) { s1.add(arr1[j]); } // Insert first Y elements into set s2 for (int j = 0; j < Y; j++) { s2.add(arr2[j]); } // If both sets are equal if (s1.equals(s2)) { System.out.println("YES"); } else { System.out.println("NO"); } } } public static void main(String[] args) { int[] arr1 = { 5, 6, 7, 8, 9 }; int[] arr2 = { 5, 6, 6, 8, 7 }; int[][] Q = { { 4, 5 }, { 3, 3 }, { 2, 3 } }; int N = arr1.length; int M = Q.length; // Function call checkEquality(arr1, arr2, N, Q, M); }}// This code is contributed by lokeshmvs21. |
Python3
# Python program for the above approach# Function to check if set of values of the# first X elements are equal to set of# values of first Y elements.def checkEquality(arr1, arr2, N, Q, M): # Iterating for each query M for i in range(M): # Query in the form [X, Y] X = Q[i][0] Y = Q[i][1] # Declaration of empty sets s1 = set() s2 = set() # Insert first X elements into set s1 for j in range(X): s1.add(arr1[j]) # Insert first Y elements into set s2 for j in range(Y): s2.add(arr2[j]) # If both sets are equal if (s1 == s2): print("YES") else: print("NO")# Driver Codearr1 = [5, 6, 7, 8, 9]arr2 = [5, 6, 6, 8, 7]Q = [[4, 5], [3, 3], [2, 3]]N = len(arr1)M = len(Q)# Function CallcheckEquality(arr1, arr2, N, Q, M)# This code is contributed by Potta Lokesh |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // Function to check if set of values of the // first X elements are equal to set of // values of first Y elements. static void checkEquality(int[] arr1, int[] arr2, int N, int[,] Q, int M) { // Iterating for each query M for (int i = 0; i < M; i++) { // Query in the form [X, Y] int X = Q[i,0], Y = Q[i,1]; // Declaration of empty sets HashSet<int> s1 = new HashSet<int>(); HashSet<int> s2 = new HashSet<int>(); // Insert first X elements into set s1 for (int j = 0; j < X; j++) { s1.Add(arr1[j]); } // Insert first Y elements into set s2 for (int j = 0; j < Y; j++) { s2.Add(arr2[j]); } // If both sets are equal if (s1.SetEquals(s2)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } } public static void Main() { int[] arr1 = { 5, 6, 7, 8, 9 }; int[] arr2 = { 5, 6, 6, 8, 7 }; int[,] Q = { { 4, 5 }, { 3, 3 }, { 2, 3 } }; int N = arr1.Length; int M = Q.GetLength(0); // Function call checkEquality(arr1, arr2, N, Q, M); }}// This code is contributed by Pushpesh Raj. |
Javascript
// JS code to implement the approach// Function to check if set of values of the// first X elements are equal to set of// values of first Y elements.function setsAreEqual(a, b) { if (a.size !== b.size) { return false; } return Array.from(a).every(element => { return b.has(element); });}function checkEquality(arr1,arr2,N,Q,M){ // Iterating for each query M for (let i = 0; i < M; i++) { // Query in the form [X, Y] let X = Q[i][0], Y = Q[i][1]; // Declaration of empty sets //set<int> s1, s2; const s1 = new Set(); const s2 = new Set(); // Insert first X elements into set s1 for (let j = 0; j < X; j++) { s1.add(arr1[j]); } // Insert first Y elements into set s2 for (let j = 0; j < Y; j++) { s2.add(arr2[j]); } if(setsAreEqual(s1,s2)==true) console.log("YES"); else{ console.log("NO"); } }}// Driver Code let arr1 = [ 5, 6, 7, 8, 9 ]; let arr2 = [ 5, 6, 6, 8, 7 ]; let Q = [ [ 4, 5 ], [ 3, 3 ], [ 2, 3 ] ]; let N = arr1.length; let M = Q.length; // Function Call checkEquality(arr1, arr2, N, Q, M); // This code is contributed by ksam24000. |
Output
YES NO YES
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Efficient Approach: The above approach can be optimized based on the following idea:
This problem can be solved using Zobrist Hash, which is a probabilistic algorithm to determine if two sets are equal.
In Zobrist Hash we assign random value to each number then check whether their XOR equal or not. We will use Zobrist Hash with prefix XOR array to be able to tell xor of first N elements in constant time for each query. if XOR of the first X element of arr1[] is equal to XOR of first Y elements of arr2[]then they are same set so print “YES” else “NO“.
Follow the steps below to solve the problem:
- Making Prefix XOR arrays pre1[] and pre2[] for arr1[] and arr2[] for precomputation of XOR of first n distinct elements
- Declaring two sets for arr1[] and arr2[]. Once we take Xor of element x, we will push it into these sets to avoid taking xor of the same element again.
- Declare hash map numberGenerated for storing random numbers generated. So each number will have a unique random number.
- Precompute prefix xor array for both arr1[] and arr2[].
- For each query store xor of first X elements in xorOfFirstX and xor of first Y elements in xorOfFirstY.
- If they are equal print “YES” else print “NO”.
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 set of values of the// first X elements are equal to set of// values of first Y elements of arr1[] and// arr2[]void checkEquality(int arr1[], int arr2[], int N, int Q[][2], int M){ // Making prefix sum array for // arr1[] and arr2[] for precomputation // of xor of first i distinct elements int pre1[N + 1] = { 0 }, pre2[N + 1] = { 0 }; // Declaring two sets for arr1[] and // arr2[] once we take xor of element x // we will push it into set to avoid // taking xor if it again repeats in // next iterations set<int> s1, s2; // Hash map for storing // random number generated so // each number will have unique // random number. map<int, int> numberGenerated; // Iterating from 0 to N - 1 for (int i = 0; i < N; i++) { int x = arr1[i]; // Taking prefix xor pre1[i + 1] ^= pre1[i]; // If random number is not generated // for given number than generate // using rand function if (numberGenerated.find(x) == numberGenerated.end()) numberGenerated[x] = rand(); // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (s1.find(x) == s1.end()) pre1[i + 1] ^= numberGenerated[x]; // Include x in set 1 // to avoid inclusion of x // in future s1.insert(x); } for (int i = 0; i < N; i++) { int x = arr2[i]; // Taking prefix xor pre2[i + 1] ^= pre2[i]; // If random number is not generated // for given number than generate // using rand function if (numberGenerated.find(x) == numberGenerated.end()) numberGenerated[x] = rand(); // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (s2.find(x) == s2.end()) pre2[i + 1] ^= numberGenerated[x]; // Include x in set 2 // to avoid inclusion of x // in future s2.insert(x); } // Iterating for each query M for (int i = 0; i < M; i++) { // Query in the form [X, Y] int X = Q[i][0], Y = Q[i][1]; // Xor of first X elements of arr1[] int xorOfFirstX = pre1[X]; // Xor of first Y elements of arr2[] int xorOfFirstY = pre2[Y]; // If xor of first X elements of // arr1[] is equal to xor of first // Y elements of arr2[] print yes // else no if (xorOfFirstX == xorOfFirstY) { cout << "YES" << endl; } // Otherwise else { cout << "NO" << endl; } }}// Driver Codeint main(){ int arr1[] = { 5, 6, 7, 8, 9 }; int arr2[] = { 5, 6, 6, 8, 7 }; int Q[][2] = { { 4, 5 }, { 3, 3 }, { 2, 3 } }; int N = sizeof(arr1) / sizeof(arr1[0]); int M = sizeof(Q) / sizeof(Q[0]); // Function Call checkEquality(arr1, arr2, N, Q, M); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG { // Function to check if set of values of the // first X elements are equal to set of // values of first Y elements of arr1[] and // arr2[] public static void checkEquality(int[] arr1, int[] arr2, int N, int[][] Q, int M) { // Making prefix sum array for // arr1[] and arr2[] for precomputation // of xor of first i distinct elements int[] pre1 = new int[N + 2], pre2 = new int[N + 2]; Arrays.fill(pre1, 0); Arrays.fill(pre2, 0); // Declaring two sets for arr1[] and // arr2[] once we take xor of element x // we will push it into set to avoid // taking xor if it again repeats in // next iterations HashSet<Integer> s1 = new HashSet<Integer>(), s2 = new HashSet<Integer>(); // Hash map for storing // random number generated so // each number will have unique // random number. HashMap<Integer, Integer> numberGenerated = new HashMap<Integer, Integer>(); // Iterating from 0 to N - 1 for (int i = 0; i < N; i++) { int x = arr1[i]; // Taking prefix xor pre1[i + 1] ^= pre1[i]; // If random number is not generated // for given number than generate // using rand function if (!numberGenerated.containsKey(x)) numberGenerated.put(x, new Random().nextInt()); // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (!s1.contains(x)) pre1[i + 1] ^= numberGenerated.get(x); // Include x in set 1 // to avoid inclusion of x // in future s1.add(x); } for (int i = 0; i < N; i++) { int x = arr2[i]; // Taking prefix xor pre2[i + 1] ^= pre2[i]; // If random number is not generated // for given number than generate // using rand function if (!numberGenerated.containsKey(x)) numberGenerated.put(x, new Random().nextInt()); // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (!s2.contains(x)) pre2[i + 1] ^= numberGenerated.get(x); // Include x in set 2 // to avoid inclusion of x // in future s2.add(x); } // Iterating for each query M for (int i = 0; i < M; i++) { // Query in the form [X, Y] int X = Q[i][0], Y = Q[i][1]; // Xor of first X elements of arr1[] int xorOfFirstX = pre1[X]; // Xor of first Y elements of arr2[] int xorOfFirstY = pre2[Y]; // If xor of first X elements of // arr1[] is equal to xor of first // Y elements of arr2[] print yes // else no if (xorOfFirstX == xorOfFirstY) { System.out.println("YES"); } // Otherwise else { System.out.println("NO"); } } } public static void main(String[] args) { int[] arr1 = { 5, 6, 7, 8, 9 }; int[] arr2 = { 5, 6, 6, 8, 7 }; int[][] Q = { { 4, 5 }, { 3, 3 }, { 2, 3 } }; int N = arr1.length; int M = Q.length; // Function Call checkEquality(arr1, arr2, N, Q, M); }}// This code is contributed by akashish__ |
Python3
import randomdef check_equality(arr1, arr2, N, Q, M): # Making prefix sum array for # arr1[] and arr2[] for precomputation # of xor of first i distinct elements pre1 = [0] * (N + 1) pre2 = [0] * (N + 1) # Declaring two sets for arr1[] and # arr2[] once we take xor of element x # we will push it into set to avoid # taking xor if it again repeats in # next iterations s1 = set() s2 = set() # Hash map for storing # random number generated so # each number will have unique # random number. number_generated = {} # Iterating from 0 to N - 1 for i in range(N): x = arr1[i] # Taking prefix xor pre1[i + 1] ^= pre1[i] # If random number is not generated # for given number than generate # using rand function if x not in number_generated: number_generated[x] = random.randint(0, 2**31) # If x did not appeared in # previous iterations take its xor # with current position which is # i + 1 if x not in s1: pre1[i + 1] ^= number_generated[x] # Include x in set 1 # to avoid inclusion of x # in future s1.add(x) for i in range(N): x = arr2[i] # Taking prefix xor pre2[i + 1] ^= pre2[i] # If random number is not generated # for given number than generate # using rand function if x not in number_generated: number_generated[x] = random.randint(0, 2**31) # If x did not appeared in # previous iterations take its xor # with current position which is # i + 1 if x not in s2: pre2[i + 1] ^= number_generated[x] # Include x in set 2 # to avoid inclusion of x # in future s2.add(x) # Iterating for each query M for i in range(M): # Query in the form [X, Y] X = Q[i][0] Y = Q[i][1] # Xor of first X elements of arr1[] xor_of_first_x = pre1[X] # Xor of first Y elements of arr2[] xor_of_first_y = pre2[Y] # If xor of first X elements of # arr1[] is equal to xor of first # Y elements of arr2[] print yes # else no if xor_of_first_x == xor_of_first_y: print("YES") # Otherwise else: print("NO")# Driver Codeif __name__ == "__main__": arr1 = [5, 6, 7, 8, 9] arr2 = [5, 6, 6, 8, 7] Q = [[4, 5], [3, 3], [2, 3]] N = len(arr1) M = len(Q) # Function Call check_equality(arr1, arr2, N, Q, M)#This code is contributed by sanjanasikarwar24 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Function to check if set of values of the // first X elements are equal to set of // values of first Y elements of arr1[] and // arr2[] public static void checkEquality(int[] arr1, int[] arr2, int N, int[, ] Q, int M) { // Making prefix sum array for // arr1[] and arr2[] for precomputation // of xor of first i distinct elements int[] pre1 = new int[N + 2], pre2 = new int[N + 2]; Array.Fill(pre1, 0); Array.Fill(pre2, 0); // Declaring two sets for arr1[] and // arr2[] once we take xor of element x // we will push it into set to avoid // taking xor if it again repeats in // next iterations HashSet<int> s1 = new HashSet<int>(), s2 = new HashSet<int>(); // Hash map for storing // random number generated so // each number will have unique // random number. Dictionary<int, int> numberGenerated = new Dictionary<int, int>(); // Iterating from 0 to N - 1 for (int i = 0; i < N; i++) { int x = arr1[i]; // Taking prefix xor pre1[i + 1] ^= pre1[i]; // If random number is not generated // for given number than generate // using rand function if (!numberGenerated.ContainsKey(x)) numberGenerated[x] = new Random().Next(); // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (!s1.Contains(x)) pre1[i + 1] ^= numberGenerated[x]; // Include x in set 1 // to avoid inclusion of x // in future s1.Add(x); } for (int i = 0; i < N; i++) { int x = arr2[i]; // Taking prefix xor pre2[i + 1] ^= pre2[i]; // If random number is not generated // for given number than generate // using rand function if (!numberGenerated.ContainsKey(x)) numberGenerated[x] = new Random().Next(); // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (!s2.Contains(x)) pre2[i + 1] ^= numberGenerated[x]; // Include x in set 2 // to avoid inclusion of x // in future s2.Add(x); } // Iterating for each query M for (int i = 0; i < M; i++) { // Query in the form [X, Y] int X = Q[i, 0], Y = Q[i, 1]; // Xor of first X elements of arr1[] int xorOfFirstX = pre1[X]; // Xor of first Y elements of arr2[] int xorOfFirstY = pre2[Y]; // If xor of first X elements of // arr1[] is equal to xor of first // Y elements of arr2[] print yes // else no if (xorOfFirstX == xorOfFirstY) { Console.WriteLine("YES"); } // Otherwise else { Console.WriteLine("NO"); } } } // Driver Code static public void Main() { int[] arr1 = { 5, 6, 7, 8, 9 }; int[] arr2 = { 5, 6, 6, 8, 7 }; int[, ] Q = { { 4, 5 }, { 3, 3 }, { 2, 3 } }; int N = arr1.Length; int M = Q.GetLength(0); // Function Call checkEquality(arr1, arr2, N, Q, M); }}// This code is contributed by akashish__ |
Javascript
function checkEquality(arr1, arr2, N, Q, M) { // Making prefix sum array for // arr1[] and arr2[] for precomputation // of xor of first i distinct elements let pre1 = new Array(N + 1).fill(0); let pre2 = new Array(N + 1).fill(0); // Declaring two sets for arr1[] and // arr2[] once we take xor of element x // we will push it into set to avoid // taking xor if it again repeats in // next iterations let s1 = new Set(); let s2 = new Set(); // Hash map for storing // random number generated so // each number will have unique // random number. let numberGenerated = {}; // Iterating from 0 to N - 1 for (let i = 0; i < N; i++) { let x = arr1[i]; // Taking prefix xor pre1[i + 1] ^= pre1[i]; // If random number is not generated // for given number than generate // using Math.random() function if (!numberGenerated.hasOwnProperty(x)) { numberGenerated[x] = Math.floor(Math.random() * (2 ** 31)); } // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (!s1.has(x)) { pre1[i + 1] ^= numberGenerated[x]; } // Include x in set 1 // to avoid inclusion of x // in future s1.add(x); } for (let i = 0; i < N; i++) { let x = arr2[i]; // Taking prefix xor pre2[i + 1] ^= pre2[i]; // If random number is not generated // for given number than generate // using Math.random() function if (!numberGenerated.hasOwnProperty(x)) { numberGenerated[x] = Math.floor(Math.random() * (2 ** 31)); } // If x did not appeared in // previous iterations take its xor // with current position which is // i + 1 if (!s2.has(x)) { pre2[i + 1] ^= numberGenerated[x]; } // Include x in set 2 // to avoid inclusion of x // in future s2.add(x); } // Iterating for each query M for (let i = 0; i < M; i++) { // Query in the form [X, Y] let X = Q[i][0]; let Y = Q[i][1]; // Xor of first X elements of arr1[] let xorOfFirstX = pre1[X]; // Xor of first Y elements of arr2[] let xorOfFirstY = pre2[Y]; // If xor of first X elements of // arr1[] is equal if(xorOfFirstX == xorOfFirstY){ console.log("YES") } else{ console.log("NO") } }}let arr1 = [5, 6, 7, 8, 9];let arr2 = [5, 6, 6, 8, 7];let Q = [[4, 5], [3, 3], [2, 3]];let N = arr1.length;let M = Q.length;checkEquality(arr1, arr2, N, Q, M) |
Output
YES NO YES
Time Complexity: O(N*logN + M)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Arrays – Data Structures and Algorithms Tutorials
- Introduction to Hashing – Data Structures and Algorithms Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
