Given a 2-D array of order N X M array elements, the task is to check if we can select a number from every row in such a way that xor of the selected numbers is greater than 0.
Note: There is a minimum of 2 rows.
Examples:
Input: a[][] = {{7, 7, 7},
{10, 10, 7}}
Output: Yes
Input: a[][] = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}
Output: No
Approach: Initially check if xor of first column elements of every row is 0 or not. If it is non-zero then it is possible. If it is zero, check if any of the rows has two or more distinct elements, then also it is possible. If both of the above conditions are not satisfied, then it is not possible.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define N 2#define M 3// Function to check if a number from every row // can be selected such that xor of the numbers // is greater than zerobool check(int mat[N][M]){ int xorr = 0; // Find the xor of first // column for every row for (int i = 0; i < N; i++) { xorr ^= mat[i][0]; } // If Xorr is 0 if (xorr != 0) return true; // Traverse in the matrix for (int i = 0; i < N; i++) { for (int j = 1; j < M; j++) { // Check is atleast // 2 distinct elements if (mat[i][j] != mat[i][0]) return true; } } return false;}// Driver codeint main(){ int mat[N][M] = { { 7, 7, 7 }, { 10, 10, 7 } }; if (check(mat)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG { static int N = 2; static int M = 3; // Function to check if a number // from every row can be selected // such that xor of the numbers // is greater than zero static boolean check(int mat[][]) { int xorr = 0; // Find the xor of first // column for every row for (int i = 0; i < N; i++) { xorr ^= mat[i] [0]; } // If Xorr is 0 if (xorr != 0) return true; // Traverse in the matrix for (int i = 0; i < N; i++) { for (int j = 1; j < M; j++) { // Check is atleast // 2 distinct elements if (mat[i] [j] != mat[i] [0]) return true; } } return false; } // Driver code public static void main (String[] args) { int mat[][] = {{ 7, 7, 7 }, { 10, 10, 7 }}; if (check(mat)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by ajit |
Python3
# Python3 program to implement# the above approachN = 2M = 3# Function to check if a number from every row # can be selected such that xor of the numbers # is greater than zerodef check(mat): xorr = 0 # Find the xor of first # column for every row for i in range(N): xorr ^= mat[i][0] # If Xorr is 0 if (xorr != 0): return True # Traverse in the matrix for i in range(N): for j in range(1, M): # Check is atleast # 2 distinct elements if (mat[i][j] != mat[i][0]): return True return False# Driver codemat = [[ 7, 7, 7 ], [ 10, 10, 7 ]]if (check(mat)): print("Yes")else: print("No")# This code is contributed by mohit kumar |
C#
// C# program to implement// the above approachusing System;class GFG{ static int N = 2; static int M = 3; // Function to check if a number // from every row can be selected // such that xor of the numbers // is greater than zero static bool check(int [,]mat) { int xorr = 0; // Find the xor of first // column for every row for (int i = 0; i < N; i++) { xorr ^= mat[i, 0]; } // If Xorr is 0 if (xorr != 0) return true; // Traverse in the matrix for (int i = 0; i < N; i++) { for (int j = 1; j < M; j++) { // Check is atleast // 2 distinct elements if (mat[i, j] != mat[i, 0]) return true; } } return false; } // Driver code static void Main() { int [,]mat = {{ 7, 7, 7 }, { 10, 10, 7 }}; if (check(mat)) Console.Write("Yes"); else Console.Write("No"); }}// This code is contributed by mits |
PHP
<?php// PHP program to implement// the above approach$N = 2;$M = 3;// Function to check if a number from every row // can be selected such that xor of the numbers // is greater than zerofunction check($mat){ global $N ; global $M ; $xorr = 0; // Find the xor of first // column for every row for ($i = 0; $i < $N; $i++) { $xorr = $xorr ^ $mat[$i][0]; } // If Xorr is 0 if ($xorr != 0) return true; // Traverse in the matrix for ($i = 0; $i < $N; $i++) { for ( $j = 1; $j < $M; $j++) { // Check is atleast // 2 distinct elements if ($mat[$i][$j] != $mat[$i][0]) return true; } } return false;} // Driver code $mat = array(array( 7, 7, 7 ), array( 10, 10, 7 )); if (check($mat)) echo "Yes"; else echo "No";// This code is contributed by Tushil..?> |
Javascript
<script>// Javascript program to implement// the above approachlet N = 2;let M = 3;// Function to check if a number from every row // can be selected such that xor of the numbers // is greater than zerofunction check(mat){ let xorr = 0; // Find the xor of first // column for every row for (let i = 0; i < N; i++) { xorr ^= mat[i][0]; } // If Xorr is 0 if (xorr != 0) return true; // Traverse in the matrix for (let i = 0; i < N; i++) { for (let j = 1; j < M; j++) { // Check is atleast // 2 distinct elements if (mat[i][j] != mat[i][0]) return true; } } return false;}// Driver code let mat = [ [ 7, 7, 7 ], [ 10, 10, 7 ] ]; if (check(mat)) document.write("Yes"); else document.write("No");// This code is contributed by souravmahato348.</script> |
Output:
Yes
Time Complexity: O(N * M)
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!