Given a binary matrix mat[][] of dimension N*M, the task is to check if all 1s in each row are placed adjacently on the given matrix. If all 1s in each row are adjacent, then print “Yes”. Otherwise, print “No”.
Examples:
Input: mat[][] = {{0, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}, {1, 1, 1, 0}
Output: Yes
Explanation:
Elements in the first row are {0, 1, 1, 0}.
Elements in the 2nd row are {1, 1, 0, 0}.
Elements in the 3rd row are {0, 0, 0, 1}.
Elements in the 4th row are {1, 1, 1, 0}.
Therefore, all the rows have all 1s grouped together. Therefore, print Yes.Input: mat[][] = {{1, 0, 1}, {0, 0, 1}, {0, 0, 0}}
Output: No
Approach: The idea is to perform row-wise traversal on the matrix and check if all the 1s in a row are placed adjacently or not by using the property of Bitwise XOR. The given problem can be solved based on the following observations:
- Calculate the sum of Bitwise XOR of every pair of adjacent elements of ith row, say X. All 1s will be not together in the ith row if any of the following conditions are satisfied:
- If X > 2 and mat[i][0] + mat[i][M – 1] = 0.
- If X > 1 and mat[i][0] + mat[i][M – 1] = 1.
- If X > 0 and mat[i][0] + mat[i][M – 1] = 0.
Follow the steps below to solve this problem:
- Traverse the given matrix mat[][] and perform the following operations:
- For each row, check if the value of M is less than 3, then print “Yes”.
- Otherwise, find the sum of Bitwise XOR of adjacent array elements and store it in a variable, say X.
- For every value of X, if any of the above-mentioned conditions holds true, then print “No”.
- After completing the above steps, if any of the above conditions does not hold true for any value of X, then 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 check if all 1s are// placed adjacently in an array or notbool checkGroup(vector<int> arr){ // Base Case if (arr.size() <= 2) return true; int corner = arr[0] + arr[(int)arr.size()-1]; // Stores the sum of XOR of all // pair of adjacent elements int xorSum = 0; // Calculate sum of XOR of all // pair of adjacent elements for (int i = 0; i < arr.size() - 1; i++) xorSum += (arr[i] ^ arr[i + 1]); // Check for corner cases if (!corner) if (xorSum > 2) return false; else if (corner == 1) if (xorSum > 1) return false; else if (xorSum > 0) return false; // Return true return true;}// Function to check if all the rows// have all 1s grouped together or notbool isInGroupUtil(vector<vector<int>> mat){ // Traverse each row for (auto i:mat) { // Check if all 1s are placed // together in the ith row or not if (!checkGroup(i)) return false; } return true;}// Function to check if all 1s in a row// are grouped together in a matrix or notvoid isInGroup(vector<vector<int>> mat){ bool ans = isInGroupUtil(mat); //Print the result if (ans) printf("Yes"); else printf("No");}// Driver Codeint main(){ // Given matrix vector<vector<int>> mat = {{0, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}, {1, 1, 1, 0}}; // Function Call isInGroup(mat);}// This code is contributed by mohit kumar 29. |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Function to check if all 1s are // placed adjacently in an array or not static Boolean checkGroup(Vector<Integer> arr) { // Base Case if (arr.size() <= 2) return true; int corner = arr.get(0) + arr.get(arr.size()-1); // Stores the sum of XOR of all // pair of adjacent elements int xorSum = 0; // Calculate sum of XOR of all // pair of adjacent elements for (int i = 0; i < arr.size() - 1; i++) xorSum += (arr.get(i) ^ arr.get(i + 1)); // Check for corner cases if (corner == 0) if (xorSum > 2) return false; else if (corner == 1) if (xorSum > 1) return false; else if (xorSum > 0) return false; // Return true return true; } // Function to check if all the rows // have all 1s grouped together or not static Boolean isInGroupUtil(int[][] mat) { // Traverse each row for (int i = 0; i < mat.length; i++) { Vector<Integer> arr = new Vector<Integer>(); for(int j = 0; j < mat[i].length; j++) { arr.add(mat[i][j]); } // Check if all 1s are placed // together in the ith row or not if (!checkGroup(arr)) return false; } return true; } // Function to check if all 1s in a row // are grouped together in a matrix or not static void isInGroup(int[][] mat) { Boolean ans = isInGroupUtil(mat); //Print the result if (ans) System.out.print("Yes"); else System.out.print("No"); } public static void main(String[] args) { // Given matrix int[][] mat = {{0, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}, {1, 1, 1, 0}}; // Function Call isInGroup(mat); }}// This code is contributed by decode2207. |
Python3
# Python3 program for the above approach# Function to check if all 1s are# placed adjacently in an array or notdef checkGroup(arr): # Base Case if len(arr) <= 2: return True corner = arr[0] + arr[-1] # Stores the sum of XOR of all # pair of adjacent elements xorSum = 0 # Calculate sum of XOR of all # pair of adjacent elements for i in range(len(arr)-1): xorSum += (arr[i] ^ arr[i + 1]) # Check for corner cases if not corner: if xorSum > 2: return False elif corner == 1: if xorSum > 1: return False else: if xorSum > 0: return False # Return true return True# Function to check if all the rows# have all 1s grouped together or notdef isInGroupUtil(mat): # Traverse each row for i in mat: # Check if all 1s are placed # together in the ith row or not if not checkGroup(i): return False return True# Function to check if all 1s in a row# are grouped together in a matrix or notdef isInGroup(mat): ans = isInGroupUtil(mat) # Print the result if ans: print("Yes") else: print("No")# Given matrixmat = [[0, 1, 1, 0], [1, 1, 0, 0], [0, 0, 0, 1], [1, 1, 1, 0]]# Function CallisInGroup(mat) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if all 1s are // placed adjacently in an array or not static bool checkGroup(List<int> arr) { // Base Case if (arr.Count <= 2) return true; int corner = arr[0] + arr[arr.Count-1]; // Stores the sum of XOR of all // pair of adjacent elements int xorSum = 0; // Calculate sum of XOR of all // pair of adjacent elements for (int i = 0; i < arr.Count - 1; i++) xorSum += (arr[i] ^ arr[i + 1]); // Check for corner cases if (corner == 0) if (xorSum > 2) return false; else if (corner == 1) if (xorSum > 1) return false; else if (xorSum > 0) return false; // Return true return true; } // Function to check if all the rows // have all 1s grouped together or not static bool isInGroupUtil(int[,] mat) { // Traverse each row for (int i = 0; i < mat.GetLength(1); i++) { List<int> arr = new List<int>(); for(int j = 0; j < mat.GetLength(0); j++) { arr.Add(mat[i,j]); } // Check if all 1s are placed // together in the ith row or not if (!checkGroup(arr)) return false; } return true; } // Function to check if all 1s in a row // are grouped together in a matrix or not static void isInGroup(int[,] mat) { bool ans = isInGroupUtil(mat); //Print the result if (ans) Console.WriteLine("Yes"); else Console.WriteLine("No"); } // Driver code static void Main() { // Given matrix int[,] mat = {{0, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 0, 1}, {1, 1, 1, 0}}; // Function Call isInGroup(mat); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script> // Javascript program for the above approach // Function to check if all 1s are // placed adjacently in an array or not function checkGroup(arr) { // Base Case if (arr.length <= 2) return true; let corner = arr[0] + arr[arr.length-1]; // Stores the sum of XOR of all // pair of adjacent elements let xorSum = 0; // Calculate sum of XOR of all // pair of adjacent elements for (let i = 0; i < arr.length - 1; i++) xorSum += (arr[i] ^ arr[i + 1]); // Check for corner cases if (corner == 0) if (xorSum > 2) return false; else if (corner == 1) if (xorSum > 1) return false; else if (xorSum > 0) return false; // Return true return true; } // Function to check if all the rows // have all 1s grouped together or not function isInGroupUtil(mat) { // Traverse each row for (let i = 0; i < mat.length; i++) { let arr = [] for(let j = 0; j < mat[i].length; j++) { arr.push(mat[i][j]); } // Check if all 1s are placed // together in the ith row or not if (!checkGroup(arr)) return false; } return true; } // Function to check if all 1s in a row // are grouped together in a matrix or not function isInGroup(mat) { let ans = isInGroupUtil(mat); //Print the result if (ans) document.write("Yes"); else document.write("No"); } // Given matrix let mat = [[0, 1, 1, 0], [1, 1, 0, 0], [0, 0, 0, 1], [1, 1, 1, 0]]; // Function Call isInGroup(mat);// This code is contributed by mukesh07.</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!
