There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too
Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles
Note 1: Can be done in O(N^2) time and O(1) space.
Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)
Update (Dec 20, 2010):
Complete solution posted jointly by Siddhant Agarwal (EE, Final year student, IITB) and Gaurav Sinha (IITK 1996 CSE Alumnus, IRS Officer). Thanks a lot