wu :: forums « wu :: forums - Make row/col 1 if element is 1 in a matrix. » Welcome, Guest. Please Login or Register. May 14th, 2024, 11:21pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: Grimbal, Icarus, william wu, Eigenray, towr, SMQ, ThudnBlunder)    Make row/col 1 if element is 1 in a matrix. « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Make row/col 1 if element is 1 in a matrix.  (Read 2950 times) Ved Junior Member     Gender: Posts: 53 Make row/col 1 if element is 1 in a matrix.   « on: Sep 4th, 2011, 7:45am » Quote Modify Input is a matrix of size n x m of 0s and 1s.   eg: 1 0 0 1 0 0 1 0 0 0 0 0   If a location has 1; make all the elements of that row and column = 1. eg   1 1 1 1 1 1 1 1 1 0 1 1   Solution should be with Time complexity = O(n*m) and O(1) extra space IP Logged wiley Newbie     Posts: 12 Re: Make row/col 1 if element is 1 in a matrix.   « Reply #1 on: Sep 4th, 2011, 8:33am » Quote Modify is it a binary matrix? Can we put some other number in matrix, say, 2. IP Logged wiley Newbie     Posts: 12 Re: Make row/col 1 if element is 1 in a matrix.   « Reply #2 on: Sep 4th, 2011, 8:49am » Quote Modify One soln could be: 1 0 0 1 0 0 1 0 0 0 0 0     Step1: Bring 1 to first row and first column and set everywhere else to 0. O(n*m), we'll get: 1 0 1 1 1 0 0 0 0 0 0 0   Step2: Starting from 2nd column to last column, fill columns with 1: 1 0 1 1 1 0 1 1 0 0 1 1   Step3: Starting from first row to last row fill rows with 1: 1 1 1 1 1 1 1 1 0 0 1 1   Step4: Fill for column at first index: 1 1 1 1 1 1 1 1 1 0 1 1   IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Make row/col 1 if element is 1 in a matrix.   « Reply #3 on: Sep 4th, 2011, 11:56am » Quote Modify Nice solution.   The top-left corner has to be treated as an exception in step 1; for example if the left column is zero but the top row has a one somewhere, you don't want to set the top-left corner to 1, because then the left column would become one in step 4, which wouldn't be correct (unless every row had a 1 in it). IP Logged Wikipedia, Google, Mathworld, Integer sequence DB wiley Newbie     Posts: 12 Re: Make row/col 1 if element is 1 in a matrix.   « Reply #4 on: Sep 5th, 2011, 7:30am » Quote Modify yeah.. i also got this missing case after posting the solution.. we can handle it by keeping two boolean variables, say, isColumn and isRow and set them true as applicable. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board