I'm having one binary string and have to calculate the number of zeros in that string
i know we can solve it with linear time but i want solution with o(k)
where k is number of zeros in string.
N be the length of String 1<=N<10^6
Asked
Active
Viewed 293 times
0
-
By o(k) you mean O(1) -- constant complexity or O(n) -- linear complexity? – sticky bit May 06 '18 at 05:11
-
see https://stackoverflow.com/a/8871279/7629882 – Arash Etemad May 06 '18 at 05:13
-
k means number of zeros in string – Abhijeet Gulve May 06 '18 at 05:18
-
@arash the solution they given will applicable for numbers which can be represented in binary but in my case binary string length is larger so we can not represent it in decimal format – Abhijeet Gulve May 06 '18 at 05:26
-
You can take 32/64 bits at a time and convert them into integers, and then follow that procedure. – cs95 May 06 '18 at 05:31
-
Possible duplicate of [Count number of 1's in binary representation](https://stackoverflow.com/questions/8871204/count-number-of-1s-in-binary-representation) – Charles Shiller May 06 '18 at 05:43
2 Answers
4
Given a string of N independent bits, you will have to look at each bit at least once. This gives a time complexity of O(N). There is no way to do it asymptotically faster.
The algorithms given in the mentioned questions assume, that the whole bit string fits into a word and can be handled in O(1). This does not hold, if the string can be arbitrarily long.
Henry
- 42,982
- 7
- 68
- 84
1
You can use Hamming weight algorithm, actually calculate hamming distance of the string then subtract from the size of your binary string (N)
Arash Etemad
- 1,827
- 1
- 13
- 29