Another quickie.
A string of bits is called balanced if the number of times "01" appears is same as the number of times "10" appears in the string.
For example, in "0010010", 01 appears twice ("0010010") and 10 appears twice ("0010010"), so it is balanced.
So, the question is, given a bit string of n bits (as an array of bits), can you give a sub-linear time algorithm to determine if the bit string is balanced?
[Solution]
A string of bits is called balanced if the number of times "01" appears is same as the number of times "10" appears in the string.
For example, in "0010010", 01 appears twice ("0010010") and 10 appears twice ("0010010"), so it is balanced.
So, the question is, given a bit string of n bits (as an array of bits), can you give a sub-linear time algorithm to determine if the bit string is balanced?
[Solution]
No comments:
Post a Comment