Given two arrays R[] and C[] consisting of N integers such that a matrix of dimensions N x N can be formed whose element at index (i, j) is given by (R[i] + C[j]) for all possible pairs from the two arrays. Given a matrix Queries[][] with each row representing a query of the type {A, B, X, Y}, the task for each query is to check whether there exists a path from the cell (A, B) to (X, Y) in the matrix consisting of only even numbers or not. If found to be true, print “Yes”. Otherwise, print “No”.
Note: For a path from current cell (i, j) the only possible moves are (i + 1, j), (i, j + 1), (i – 1, j), and (i, j – 1).
Examples:
Input: R[] = {6, 2, 7, 8, 3}, C[] = {3, 4, 8, 5, 1}, Queries[][] = {{2 2 1 3}, {4 2 4 3}, {5 1 3 4}}
Output: Yes Yes No
Explanation:
The matrix formed is:
{{9, 10, 14, 11, 7}
{5, 6, 10, 7, 3}
{10, 11, 15, 12, 8}
{11, 12, 16, 13, 9}
{6, 7, 11, 8, 4}}
Query1: There exist a path with even number from cell (2, 2) to (1, 3) with all cell as even number. The path is (2, 2) -> (2, 3) -> (1, 3).
Query2: There exist a path with even number from cell (4, 2) to (4, 3) with all cell as even number. The path is (4, 2) -> (4, 3).
Query3: No path exists with all elements even.Input: R[] = {1, 2, 4, 8, 5}, C[] = {2, 5, 9, 7, 6}, Queries[][] = {{2 2 1 3}, {1 4 1 3}, {5 1 3 4}}
Output: No Yes No
Explanation:
The matrix formed is:
{{3, 6, 10, 8, 7}
{4, 7, 11, 9, 8}
{6, 9, 13, 11, 10}
{10, 13, 17, 15, 14}
{7, 10, 14, 12, 11}}
Query1: No path exists with all elements even.
Query2: There exist a path with even number from cell (1, 4) to (1, 3) with all cell as even number. The path is (1, 4) -> (1, 3).
Query3: No path exists with all elements even.
Approach: The idea is to precompute the prefix sum of arrays R[] and C[] and then check for the valid path with the given conditions. Below are the steps:
- The idea is to iterate from the cell (r, c) to (r + 1, c) only if the parity of R[r] and R[r + 1] are the same because there is only one element changing.
- Similarly, do for columns from (r, c) to (r, c + 1), the parity of C and C should be the same.
- Perform the above operations for (r – 1, c) and (r, c – 1).
- Now, for each query, proceeds by checking if all elements of R[] from r = (min(A, B) to max(A, B)) have the same parity and all elements of C[] from c = (min(X, Y) to max(X, Y)) have the same parity. This can be checked in O(1) time per query by precomputing the prefix sum of parity of elements.
- If the above condition found to be true for all the cells then print “Yes” Otherwise print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find whether the path // exists with all element even or not void answerQueries(int n, int q, vector<int>& a, vector<int>& b, vector<vector<int> >& Queries) { // Add 0 to beginning to make // 1-based-indexing a.insert(a.begin(), 0); b.insert(b.begin(), 0); // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for (int i = 1; i <= n; i++) { // Taking & to check parity if (a[i] & 1) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for (int i = 1; i <= n; i++) { // Taking & to check parity if (b[i] & 1) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[][] for (int i = 0; i < q; i++) { int ra = Queries[i][0]; int ca = Queries[i][1]; int rb = Queries[i][2]; int cb = Queries[i][3]; int r2 = max(ra, rb), r1 = min(ra, rb); int c2 = max(ca, cb), c1 = min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists cout << "Yes" << ' '; continue; } } // No path exists cout << "No" << ' '; } } // Driver Code int main() { // Given N, Q int N = 5, Q = 3; // Given array R[] and C[] vector<int> R{ 6, 2, 7, 8, 3 }; vector<int> C{ 3, 4, 8, 5, 1 }; // Given queries[][] vector<vector<int> > Queries{ { 2, 2, 1, 3 }, { 4, 2, 4, 3 }, { 5, 1, 3, 4 } }; // Function Call answerQueries(N, Q, R, C, Queries); return 0; } |
Java
// Java program for the above approach import java.util.*;import java.lang.*;import java.io.*;class GFG{ // Function to find whether the path // exists with all element even or not static void answerQueries(int n, int q, int[] a, int[] b, int[][] Queries) { // Add 0 to beginning to make // 1-based-indexing // a[0]=0; // b[0]=0; // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((a[i] & 1) != 0) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((b[i] & 1) != 0) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[][] for(int i = 0; i < q; i++) { int ra = Queries[i][0]; int ca = Queries[i][1]; int rb = Queries[i][2]; int cb = Queries[i][3]; int r2 = Math.max(ra, rb), r1 = Math.min(ra, rb); int c2 = Math.max(ca, cb), c1 = Math.min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists System.out.print("Yes" + " "); continue; } } // No path exists System.out.print("No" + " "); } } // Driver Code public static void main (String[] args) throws java.lang.Exception{ // Given N, Q int N = 5, Q = 3; // Given array R[] and C[] int R[] = { 0, 6, 2, 7, 8, 3 }; int C[] = { 0, 3, 4, 8, 5, 1 }; // Given queries[][] int[][] Queries = { { 2, 2, 1, 3 }, { 4, 2, 4, 3 }, { 5, 1, 3, 4 }}; // Function call answerQueries(N, Q, R, C, Queries); }}// This code is contributed by bikram2001jha |
Python3
# Python3 program for # the above approach# Function to find whether the path# exists with all element even or notdef answerQueries(n, q, a, b, Queries): # Add 0 to beginning to make # 1-based-indexing # a[0]=0; # b[0]=0; # Change elements based on parity # and take prefix sum # 1 is odd and 0 is even # Traverse the array R for i in range(1, n + 1): # Taking & to check parity if ((a[i] & 1) != 0): a[i] = 1; else: a[i] = 0; # Build prefix sum array a[i] += a[i - 1]; # Traverse the array C for i in range(1, n + 1): # Taking & to check parity if ((b[i] & 1) != 0): b[i] = 1; else: b[i] = 0; # Build prefix sum array b[i] += b[i - 1]; # Traverse the matrix Queries for i in range(0, q): ra = Queries[i][0]; ca = Queries[i][1]; rb = Queries[i][2]; cb = Queries[i][3]; r2 = max(ra, rb); r1 = min(ra, rb); c2 = max(ca, cb); c1 = min(ca, cb); # Check if all numbers are of # same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) or (a[r2] - a[r1 - 1] == r2 - r1 + 1)): # Check if all numbers are of # same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) or (b[c2] - b[c1 - 1] == c2 - c1 + 1)): # Path exists print("Yes", end = " "); continue; # No path exists print("No", end = " ");# Driver Codeif __name__ == '__main__': # Given N, Q N = 5; Q = 3; # Given array R and C R = [0, 6, 2, 7, 8, 3]; C = [0, 3, 4, 8, 5, 1]; # Given queries Queries = [[2, 2, 1, 3], [4, 2, 4, 3], [5, 1, 3, 4]]; # Function call answerQueries(N, Q, R, C, Queries);# This code is contributed by shikhasingrajput |
C#
// C# program for // the above approach using System;class GFG{ // Function to find whether the path // exists with all element even or not static void answerQueries(int n, int q, int[] a, int[] b, int[,] Queries) { // Add 0 to beginning to make // 1-based-indexing // a[0]=0; // b[0]=0; // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((a[i] & 1) != 0) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for(int i = 1; i <= n; i++) { // Taking & to check parity if ((b[i] & 1) != 0) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[,] for(int i = 0; i < q; i++) { int ra = Queries[i, 0]; int ca = Queries[i, 1]; int rb = Queries[i, 2]; int cb = Queries[i, 3]; int r2 = Math.Max(ra, rb), r1 = Math.Min(ra, rb); int c2 = Math.Max(ca, cb), c1 = Math.Min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists Console.Write("Yes" + " "); continue; } } // No path exists Console.Write("No" + " "); } } // Driver Code public static void Main(String[] args){ // Given N, Q int N = 5, Q = 3; // Given array R[] and C[] int []R = {0, 6, 2, 7, 8, 3}; int []C = {0, 3, 4, 8, 5, 1}; // Given [,]queries int[,] Queries = {{2, 2, 1, 3}, {4, 2, 4, 3}, {5, 1, 3, 4}}; // Function call answerQueries(N, Q, R, C, Queries); }}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to implement// the above approach // Function to find whether the path // exists with all element even or not function answerQueries(n, q, a, b,Queries) { // Add 0 to beginning to make // 1-based-indexing // a[0]=0; // b[0]=0; // Change elements based on parity // and take prefix sum // 1 is odd and 0 is even // Traverse the array R[] for(let i = 1; i <= n; i++) { // Taking & to check parity if ((a[i] & 1) != 0) a[i] = 1; else a[i] = 0; // Build prefix sum array a[i] += a[i - 1]; } // Traverse the array C[] for(let i = 1; i <= n; i++) { // Taking & to check parity if ((b[i] & 1) != 0) b[i] = 1; else b[i] = 0; // Build prefix sum array b[i] += b[i - 1]; } // Traverse the matrix Queries[][] for(let i = 0; i < q; i++) { let ra = Queries[i][0]; let ca = Queries[i][1]; let rb = Queries[i][2]; let cb = Queries[i][3]; let r2 = Math.max(ra, rb), r1 = Math.min(ra, rb); let c2 = Math.max(ca, cb), c1 = Math.min(ca, cb); // Check if all numbers are of // same parity between (r1 to r2) if ((a[r2] - a[r1 - 1] == 0) || (a[r2] - a[r1 - 1] == r2 - r1 + 1)) { // Check if all numbers are of // same parity between (r1 to r2) if ((b[c2] - b[c1 - 1] == 0) || (b[c2] - b[c1 - 1] == c2 - c1 + 1)) { // Path exists document.write("Yes" + " "); continue; } } // No path exists document.write("No" + " "); } } // Driver Code // Given N, Q let N = 5, Q = 3; // Given array R[] and C[] let R = [0, 6, 2, 7, 8, 3 ]; let C = [0, 3, 4, 8, 5, 1 ]; // Given queries[][] let Queries = [[2, 2, 1, 3], [4, 2, 4, 3 ], [5, 1, 3, 4 ]]; // Function call answerQueries(N, Q, R, C, Queries); // This code is contributed by avijitmondal1998.</script> |
Output
Yes Yes No
Time Complexity: O(N + Q)
Auxiliary Space: O(1)
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!
