Saurabh
BAN USERAfter reading all the comments, I feel the answer is not perfect!
Point to be noted here is that the input is unlimited. There is no end to it, say you are reading a stream of data from some source. So finding the end (whether actual end or where the number becomes greater than what we were searching for), is not possible. Hence, we cannot apply binary search directly!
I suggest the following solution:
1. Take i=0
2. If 2^i <= key && 2^(i+1) > key, then we have found the range, else increment i.
3. Once the range is found (say indexes r1 and r2), there are two conditions that are possible
a. value at r1 == key, or
b. value at r1 is less than key.
if condition a then,
we can do a binary search* to find the last index of the key.
if condition b then,
we can do a binary search to find some index of key (to make it like condition a)
and then do a binary search* to find the last index.
Note: binary search* => a modified version of binary search where we find the index of input change, to find the last index.
I think this will cover the all the cases of input and give a O(log n) solution. If I am missing anything or have made a mistake, please leave a comment.
I think this is correct! Even Learncpp.com also suggest the same reason. Just to rephrase it, we assign derived class objects to base class pointers so that we have a generic way of accessing all derived objects. But this limits the access to base class part of information in the derived class objects. In order to have base class pointers access derived class data access in the derived class objects assigned to it, we use virtual function!
- Saurabh November 13, 2012
Your runtime calculation is not linear. You have a while loop in your Count2s method which depends on the number of digits in n. So essentially you are going through each number once and then calculating its number of digits (Number of digits and number of loops for the biggest number 'n' will be log10 n). Worst case the time complexity should be O (n Log10 n)
- Saurabh November 27, 2015