Given a binary matrix mat[][] of dimensions M x N and two-person P1, P2, the task is to find the person who finishes last in choosing a 0 from the matrix which changes to 1 only if the row or column of the cell consisting of 0 has one or more than one 1 in the matrix.
Note: P1 starts picking the 0s first and both the persons want to finish last. The given matrix will always have at least one 0 which could be chosen.
Examples:
Input: mat[][] = {{1, 0, 0}, {0, 0, 0}, {0, 0, 1}}
Output: P1
Explanation:
P1 chooses mat[1][1], then the matrix becomes {{1, 0, 0}, {0, 1, 0}, {0, 0,1}}.
P2 has no 0 left to choose from. So, P1 finishes last.Input: mat[][] = {{0, 0}, {0, 0}}
Output: P2
Explanation:
No matter P1 chooses which 0 P2 will always have a 0 to choose and
after P2 picks a 0 there will not be any other 0 to choose from.
Approach: The idea is based on the observation that a 0 can’t be taken if either of its row or column has 1. Follow the steps below to solve this problem:
- Initialize two sets, rows & cols to count the number of rows and columns which does not contain any 1.
- Traverse the matrix and add rows and columns having 1 in it in the set.
- Take the minimum number of rows or columns as if either of them becomes zero so that no more 0s can be taken.
- After finding the minimum number of rows and columns available, if the number of choices made is odd then P1 finishes last otherwise, P2 finishes last.
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 the person// who will finish lastvoid findLast(int mat[][3]){ int m = 3; int n = 3; // To keep track of rows // and columns having 1 set<int> rows; set<int> cols; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (mat[i][j]) { rows.insert(i); cols.insert(j); } } } // Available rows and columns int avRows = m - rows.size(); int avCols = n - cols.size(); // Minimum number of choices we have int choices = min(avRows, avCols); // If number of choices are odd if (choices & 1) // P1 will finish last cout << "P1"; // Otherwise, P2 will finish last else cout << "P2";}// Given matrixint main(){ int mat[][3] = { { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 } }; findLast(mat);}// This code is contributed by ukasp. |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG{ // Function to find the person// who will finish laststatic void findLast(int mat[][]){ int m = 3; int n = 3; // To keep track of rows // and columns having 1 Set<Integer> rows = new HashSet<Integer>(); Set<Integer> cols = new HashSet<Integer>(); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if ((mat[i][j] > 0)) { rows.add(i); cols.add(j); } } } // Available rows and columns int avRows = m - rows.size(); int avCols = n - cols.size(); // Minimum number of choices we have int choices = Math.min(avRows, avCols); // If number of choices are odd if ((choices & 1) != 0) // P1 will finish last System.out.println("P1"); // Otherwise, P2 will finish last else System.out.println("P2");}// Driver codepublic static void main (String[] args){ int mat[][] = { { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 } }; findLast(mat);}}// This code is contributed by jana_sayantan |
Python3
# Python3 program for the above approach# Function to find the person# who will finish lastdef findLast(mat): m = len(mat) n = len(mat[0]) # To keep track of rows # and columns having 1 rows = set() cols = set() for i in range(m): for j in range(n): if mat[i][j]: rows.add(i) cols.add(j) # Available rows and columns avRows = m-len(list(rows)) avCols = n-len(list(cols)) # Minimum number of choices we have choices = min(avRows, avCols) # If number of choices are odd if choices & 1: # P1 will finish last print('P1') # Otherwise, P2 will finish last else: print('P2')# Given matrixmat = [[1, 0, 0], [0, 0, 0], [0, 0, 1]]findLast(mat) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the person// who will finish laststatic void findLast(int[,] mat){ int m = 3; int n = 3; // To keep track of rows // and columns having 1 HashSet<int> rows = new HashSet<int>(); HashSet<int> cols = new HashSet<int>(); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if ((mat[i,j] > 0)) { rows.Add(i); cols.Add(j); } } } // Available rows and columns int avRows = m - rows.Count; int avCols = n - cols.Count; // Minimum number of choices we have int choices = Math.Min(avRows, avCols); // If number of choices are odd if ((choices & 1) != 0) // P1 will finish last Console.WriteLine("P1"); // Otherwise, P2 will finish last else Console.WriteLine("P2");} // Driver codestatic public void Main(){ int[,] mat = { { 1, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 } }; findLast(mat);}}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program for the above approach // Function to find the person // who will finish last function findLast( mat) { let m = mat.length; let n = mat[0].length; // To keep track of rows // and columns having 1 let rows = new Set(); let cols = new Set(); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (mat[i][j]) { rows.add(i); cols.add(j); } } } // Available rows and columns let avRows = m - rows.size; let avCols = n - cols.size; // Minimum number of choices we have let choices = Math.min(avRows, avCols); // If number of choices are odd if (choices & 1) // P1 will finish last document.write("P1") // Otherwise, P2 will finish last else document.write("P2") } // Given matrix let mat = [ [ 1, 0, 0], [ 0, 0, 0 ], [ 0, 0, 1 ]] findLast(mat); // This code is contributed by Hritik </script> |
Output:
P1
Time Complexity: O(M*N)
Auxiliary Space: O(M*N)
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!
