CareerCup

There are a couple of key points here:
1. Two equivalent binary strings are still equivalent no matter which column you remove.
2. There is no way to choose a column from n binary strings of m bits such that two or more members of N become equivalent unless m > n or unless N already has duplicates in it (see point #1).

Coded solution below...

function dups(array) {
"use strict"
        hashmap = {}
        for (i = 0; i < array.length; i++)
                if (!hashmap[array[i]])
                        hashmap[array[i]] = true
                else
                        return true

        var hashmap
        , array
        , i

        return false
}
function manhattan() {
"use strict"
        args = Array.prototype.slice.call(arguments)
        tests = args.shift()
        no = 0
        while (tests--) {
                no++
                rows = args.shift()
                cols = args.shift()
                if (rows > cols) {
                        console.log('test ' + no + ': NO')
                        continue
                }
                array = []
                for (i = 0; i < rows; i++) {
                        array.push(args.shift())
                }
                if (dups(array)) {
                        console.log('test ' + no + ': NO')
                        continue
                }
                console.log('test ' + no + ': YES')
        }

        var args
        , tests
        , rows
        , cols
        , array
        , no
        , i
}

//ex
manhattan(4
        // test1
        , 3, 3
        , 5, 0, 4 /* 0b101, 0b000, 0b100 */

        // test2
        , 2, 2
        , 3, 3 /* 0b11, 0b11 */

        // test3
        , 4, 3
        , 5, 0, 4, 7 /* 0b101, 0b000, 0b100, 0b111 */

        // test4
        , 3, 3
        , 5, 5, 4 /* 0b101, 0b101, 0b100 */
)

/*
! node manhattan.js
test 1: YES
test 2: NO
test 3: NO
test 4: NO
!
*/

Updated answer a sort of brute force-ish O(n*m) solution. Use bit masks to "remove" the column (zero it out) if their is no bit mask that can generate n unique values then the answer is no.

Note that bit operations are pretty inefficient in Javascript since the language supports no integers, but whatever.

function manhattan_ii() {

        "use strict"
        args = Array.prototype.slice.call(arguments)
        args = args.reverse()
        tests = args.pop()
        while (tests) {
                rows = args.pop()
                cols = args.pop()
                bits = ""
                for (i = 0; i < cols; ++i) {
                        bits += "1"
                }
                masks = []
                for (i = 0; i < bits.length; ++i) {
                        masks[i] = bits.split("")
                        masks[i][i] = "0"
                        masks[i] = masks[i].join("")
                        masks[i] = parseInt(masks[i], 2)
                }
                console.log(masks)
                samples = []
                for (i = 0; i < rows; ++i) {
                        samples.push(parseInt(args.pop(), 2))
                }
                bool = false
                for (i = 0; i < masks.length; ++i) {
                        hash = {}
                        for (j = 0; j < samples.length; ++j) {
                                n = masks[i] & samples[j]
                                if (hash[n]) {
                                        break
                                } else {
                                        hash[n] = true
                                }
                        }
                        if (j === samples.length) {
                                bool = true
                                break;
                        }
                }
                console.log("Test #" + tests + " : " + (bool ? "YES" : "NO"))
                tests--
        }
        var args
        , tests
        , rows
        , cols
        , bits
        , masks
        , i
        , samples
        , j
        , bool
        , hash
        ,n
}
manhattan_ii(2,3,3,"101", "000", "100", 2, 2, "11", "11")
manhattan_ii(1, 4, 3, "011", "101", "111", "100")
manhattan_ii(1, 4, 3, "110", "101", "111", "100")
manhattan_ii(1, 5, 3, "110", "110", "101", "111", "100")
manhattan_ii(1, 2, 2, "11", "10")


/* output...

! node manhattan-ii.js
[ 3, 5, 6 ]
Test #2 : YES
[ 1, 2 ]
Test #1 : NO
[ 3, 5, 6 ]
Test #1 : NO
[ 3, 5, 6 ]
Test #1 : YES
[ 3, 5, 6 ]
Test #1 : NO
[ 1, 2 ]
Test #1 : YES
!
*/

The answer is to check if all these rows are unique. If they are unique, just return true. If they are not, just return false. Because if two of the rows are the same, no matter how many columns you remove, they are still the same. If they are originally unique, no matter how many columns you remove, they are still unique.

Can You please tell me , how in the first case , that the answer is YES???

Is it like after removing the second column , the rows are 11 , 00 and 11 ?

Assuming you have input from text file (say input.txt), below is a solution in Java.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public static void main(String[] args) {
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader("input.txt"));
        } catch (FileNotFoundException e) {
            return;
        }

        try {
            int tests = Integer.parseInt(reader.readLine());
            for (int i = 0; i < tests; i++) {
                testMatrix(reader);
            }
        } catch (IOException e) {
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
            }
        }
    }

    private static void testMatrix(BufferedReader reader) throws IOException {
        String[] tokens = reader.readLine().split(" ");
        int n = Integer.parseInt(tokens[0]);
        int m = Integer.parseInt(tokens[1]);

        List<String> tmpList = new ArrayList<String>(n);
        for (int i = 0; i < n; i++) {
            tmpList.add(reader.readLine());
        }

        int columnRemoveIndex = 0;
        Set<String> tmpSet = new HashSet<String>(n);
        while (columnRemoveIndex < m) {
            tmpSet.clear();
            boolean canRemove = true;
            for (String s : tmpList) {
                StringBuilder tmpBuilder = new StringBuilder(s);
                if (!tmpSet.add(tmpBuilder.deleteCharAt(columnRemoveIndex).toString())) {
                    canRemove = false;
                    break;
                }
            }
            if (canRemove) {
                System.out.println("Yes");
                return;
            }
            columnRemoveIndex++;
        }
        System.out.println("No");
    }
}

1) Count # of1 in each row let represent it by count(i) for row i
2) If there are 2 rows exists for which count(i) - count(j) >= 2 then ans is "no" (it meas count for each row should be either x or x+1 where x is min( count(i) where 1<=i <=m)
3) Now create a column and set 0 for each row for which count(i) =x and set 1 for which count(i) = x+1
4) now search created column in matrix. If matrix has no such column then ans = "NO"
5) else if matrix has such column then remove column from matrix and check all columns of matrix IF all columns are same then ans ="yes" else ans = "NO"

The following algorithm is O(n*m^2):

- Create Flag array with the length of m. This array keep track of the column we can remove without creating similar rows.
- Set all elements of Flag to true.

- Compare every two rows:
If the are completely similar, return NO // not possible
else if they differ in one element, set the Flag of that column to false // We can not remove this column.

- If Flag has a true value, return YES
else return NO.

Here is the code, I skipped the part to read from file, and assume the data is in a n*m int[][] matrix:

public boolean canRemoveCol(int[][] matrix) {
	int n = matrix.length;
	int m = matrix[0].length;
	
	boolean[] flag = new boolean[m];
	Arrays.fill(flag, 0, m);
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			int c = -1; // c keeps track of number of different
			for (int k = 0; k < m; k++) {
				if (matrix[i][k] != matrix[j][k]) {
					if (c != -1) { // more than one different
						c = -2;
						break;
					} else {
						c = k; // first different between the two rows
					}
				}
			}
			
			if (c == -1) return false; // Found no difference between the two rows, so not possible.
			if (c > -1) flag[c] = false; // Found only one difference.
		}
	}
	
	for (int i = 0; i < m; i++) {
		if (flag[i]) return true; // We can remove this column.
	}
	
	return false;
}

First off, since each row is an m length list of binary digits, let's treat the rows as binary numbers. Take O(n) time to gather a list of n integers where the i-th integer represents the i-th row.

Next set the variable 'answer' to the value 2^(m+ 1) -1 (the number represented by m consecutive binary 1s). As we discover that the j-th column is not a candidate for removal, we'll change the j-th binary digit to 0.

Next note that there are a bunch of handy one-liners to tell if a number is a power of 2 in constant time, so that operation can be used freely. You can google it.

Now IF AND ONLY IF any two rows differ by only a singe binary digit (one row has a 0, the other has a 1) then that column for that digit is NOT a candidate for removal. Two rows differ only by the kth binary digit if the absolute value of the difference between their respective integer representations is exactly 2^k.

So now for each of the integers in our list, we find the absolute value of their difference d. If d is a power of 2 then the [k = log_2(d)]-th column is not a candidate. We mark the k-th digit in 'answer' to 0 by doing 'answer' = 'answer' & (~d). Check the difference between all of the rows.

Finding the difference between all of the rows takes time (n - 1) + (n - 2) + … + 1. This is equal to (n * (n - 1)) / 2 = (n^2 - n) / 2. Our runtime is thus O(n^2).

At the end of the day, we just check to see if 'answer' == 0. If so, no columns are candidates and we output NO. Otherwise ('answer' > 0) we output YES. Also, happy bonus info, the 1s in the binary form of 'answer' tell us which columns remain as deletion options.

Check if all the rows are unique, if not return NO (why ? Coz if two rows are not unique then removing elements in it will not make it unique)

If so then, iterate over rows find the columns which are same at each step finally remove one column from it (if more than 1 present)
Eg:
1 0 0
1 0 1
1 1 1
After 1st iteration (1 == 1, 0 == 0, 0 == 0)
1 0 0
After 2nd iteration (1 == 1, 0 == 0, 0 == 1)
1 0 -
After 3rd (nth) iteration (1 == 1, 0 == 1)
1 - -

Answer: Remove 1st column