The puzzle is here.
Problem: Given an array of n bits, can you tell if it is balanced (number of occurrences of 01 = number of occurrences of 10) in sub-linear time?
Solution
The algorithm depends on the following property:
A bit array is balanced if and only if the first and last bits are equal!
Can be proved using induction. Constant time algorithm!
Problem: Given an array of n bits, can you tell if it is balanced (number of occurrences of 01 = number of occurrences of 10) in sub-linear time?
Solution
The algorithm depends on the following property:
A bit array is balanced if and only if the first and last bits are equal!
Can be proved using induction. Constant time algorithm!
how abt this ( no induction required)
ReplyDeletereplace 0s by -1 then '01' becomes '-11' and the product of the bits is -1.
So, if a string is balanced then product of all pairwise products should be 1. Now product of all pairwise products is nothing but product of the end bits ( since all the intermediate bits are squared and hence become 1). So, for the string to be balanced the end bits should be equal.
@raghav. That is incomplete.
DeleteIf string is balanced, then end bits must be equal. Agreed.
What about the other direction?
Is it possible that an unbalanced string has end bits equal? (For instance, 5 occurences of 10 and 7 of 01)?