![]() |
#2
wfpb2007-09-15 17:39
|
Problem statement:
I have a string consisting of 0 and 1's only, say "000100101100". I want to count how many 0's are there in the string "efficiently".
Let n = length of the string. Then obviously we have O(n) algorithm.
My string will have more 0's than 1's; i.e., at least n/2+1 chars will be 0's.
My question is:
Can we do better, say O(lg n)?