..

[Ganado]

If you have an unsorted stack, as you have in your example, I don't see any way of doing O(log N) complexity. How could you know how many 1s there are without simply iterating through the list/stack? You'd have to know something about the structure/ordering of the stack in advance.

[tpb]

How can we possibly do what you ask in less than linear time?

The only possibility is to do some preprocessing while reading in the data (simply keeping track of the longest string of 1's would do here). But if you want help, you need to tell us exactly what you're trying to do.

[Ganado]

Also, the interface of the textbook stack data structure doesn't allow for random-access into the lower elements. Only the top of a stack is accessible at a given time, and 1 element is popped off at a time. OP should use a std::vector or list for simple iteration.

[tpb]

That's all you have to say?

[jonnin]

I want to break prime number encryption in O(1) too. Wanting something does not make it happen. There is no way to get your answer without touching every value at least once, which is O(N).

[Browni3141]

This problem feels like 1-dimensional battleship.

jonnin wrote:

There is no way to get your answer without touching every value at least once, which is O(N).

This is not true. Using OP's input as an example, the minimal amount of information we need to know we've found the answer is six values.

????011110??

We can avoid testing every value by segmenting the search space. For example, for the following input, our search might look like this:

0. 0110100000111110100101100011001
1. ???????????????????????????????
2. ???????????????0???????????????
3. ???????0???????0???????0???????
4. ???0???0???1???0???1???0???1???
5. ???0???0?0111110???1???0???1???
6. ???0???0?0111110??01???0??110??

0. input for reference.
1. Root. The the upper bound is 31. Our best answer is 0.
2. We've tested the middle value and it was a zero, the upper bound is 15. We've segmented the search space.
3. We've segmented the search space again. The upper bound is 7.
4. We found some 1s, now exand them to find our best answer
5. Our best answer so far is five while the upper bound is 7.
6. Our best answer is five and our maximum bound is five. The search is over after testing 15/31 values.

[helios]

Your algorithm is still O(n). There are inputs for which you'll have no choice but to evaluate the entire input. Examples:
* 00000000... (you need to make sure there are no 1s)
* 11111111... (you need to make sure there are no 0s)
* 01010101... (you need to make sure there are no longer streaks)

[Browni3141]

Your algorithm is still O(n). There are inputs for which you'll have no choice but to evaluate the entire input. Examples:
* 00000000... (you need to make sure there are no 1s)
* 11111111... (you need to make sure there are no 0s)
* 01010101... (you need to make sure there are no longer streaks)

Worst case will always be O(n). Worst case is extremely improbable if the input is random. Average case is far more interesting.

[1vRz3TCk]

Browni3141,

jonnin's reply was made before the OP change his question. At that point the OP was talking about a stack.

[Browni3141]

Browni3141,

jonnin's reply was made before the OP change his question. At that point the OP was talking about a stack.

Okay, I only saw the edited version. More information from OP would be helpful. It's hard to answer without knowing the full context.

It appears OP even edited the question again while I was making my reply. Maybe he can clear some things up for us.

[helios]

Even in your example, it's not clear to me that on average you'd get O(log n) performance. Your own example run had to hit 50% of the input. I think you should run a random statistic.

[jonnin]

I will stand by not possible for all cases unless there is more to the problem statement than we have so far. Its possible for some cases, as shown. Quite a bit more is possible if it were in integer format instead of individual bits.

[Browni3141]

helios wrote:

Even in your example, it's not clear to me that on average you'd get O(log n) performance. Your own example run had to hit 50% of the input. I think you should run a random statistic.

I was trying to avoid making the claim that my algorithm would be O(log n) in the average case because I'm lazy and didn't want to back it up. I suppose now I will though. Curse you, helios!

Why someone would report your post? Weird.

jonnin wrote:

I will stand by not possible for all cases unless there is more to the problem statement than we have so far. Its possible for some cases, as shown. Quite a bit more is possible if it were in integer format instead of individual bits.

I think it's clear that it is impossible for the best worst case to be better than O(n). Since OP didn't specify, I believe we should be looking at the average case, not the worst case. When designing algorithms most of the time the average case is more important than the worst case, as long as the performance in the worst case is acceptable. I'm just making assumptions until the OP clarifies the context of this problem.

[Ganado]

jonnin might be onto something, this might just be a communication issue.
We should clarify what "N" means here. When I said "N", I was referring to the number of digits, because OP was originally talking about elements in a stack.

But if N is the number represented by those digits, then O(log(N)) runtime is very possible, because the number N has log(N) digits. Boom. Problem solved.

Clearly logarithmic complexity because we divide n by 2 each time:

#include <iostream>

int main()
{
    int n = 0b0100'1111;
    
    int ones = 0;
    while (n > 0)
    {
        if (n % 2 == 1)
            ones++;
        n = n / 2;
    }
    
    std::cout << ones << std::endl;
} 

(That was just an example to show the number of 1s. Clearly OP has to keep track of the longest streak of 1s with another variable). What I showed should be enough to get him acclimated.

[Browni3141]

I'm not a very good coder and I screwed up the implementation of the above algorithm, but I did make an algorithm which is sub-linear in the number of bits which have to be tested.

I did a depth-first search instead of a breadth first search. The search I actually implemented looks like this:
0. 0110100000111110100101100011001
1. ???????????????????????????????
2. ???????????????0???????????????
3. ???????0???????0???????????????
4. ???0???0???????0???????????????
5. ?1?0???0???????0???????????????
6. 0110???0???????0???????????????
7. 0110?0?0???????0???????????????
8. 0110?0?0???1???0???????????????
9. 0110?0?0?0111110???????????????
A. 0110?0?0?0111110???????0???????
B. 0110?0?0?0111110???0???0???????
C. 0110?0?0?0111110???0???0???1???
D. 0110?0?0?0111110???0???0?011???

I did the average of 1000 trials per input length:

Input length: 1
Fraction of input tested: 1

Input length: 8
Fraction of input tested: 0.731125

Input length: 64
Fraction of input tested: 0.544844

Input length: 512
Fraction of input tested: 0.414082

Input length: 4096
Fraction of input tested: 0.346816

Input length: 32768
Fraction of input tested: 0.272516

Input length: 262144
Fraction of input tested: 0.206214

Input length: 2097152
Fraction of input tested: 0.189438

[helios]

Could you post the source? Use pastebin or a Github Gist if it's too long.

[Ganado]

That's pretty neat, would be interesting to calculate the actual average runtime complexity in terms of the input length. The "fraction of input tested" part at least looks like it might be 1 / log(input length) though that's a super broad guess.

[Browni3141]

I thought I shouldn't post code that could potentially be used as an answer to whatever OP is doing, but here it is. I used the function test() to check the value of a bit in the vector.

Maybe you can help out and point out any of my bad coding practices. I timed it against just counting each set bit looking for streaks and it was slightly slower for all N I tested. I guess there's more overhead than I expected.

#include <iostream>
#include <vector>

using namespace std;

int contiguousOnes(vector <bool>::iterator, vector <bool>::iterator, int);

bool test(vector <bool>::iterator);
uint64_t tests = 0;

const int TRIALS = 1000;

int main()
{
    srand(3141);
    for (int i = 0, len = 1; i < 8; i++, len *= 8)
    {
        tests = 0;
        vector <bool> input(len);
        for (int trial = 0; trial < TRIALS; trial++)
        {
            for (int index = 0; index < len; index++)
                input[index] = rand()%2;
            contiguousOnes(input.begin(), input.end()-1, 0);
        }
        cout << "Input length: " << len << '\n'
             << "Fraction of input tested: " << tests/double(TRIALS*len) << "\n";
    }
    cin.get();
    return 0;
}

int contiguousOnes(vector <bool>::iterator begin, vector <bool>::iterator end, int max)
{
    int elements = (end-begin)+1;
    if (elements <= max)
        return max;
    vector <bool>::iterator middle = begin+elements/2;
    vector <bool>::iterator leftBound, rightBound;
    if (test(middle) == 0)
    {
        leftBound = middle;
        rightBound = middle;
    }
    else
    {
        int maxTest = 1;
        for (leftBound = middle-1;  leftBound >= begin && test(leftBound) == 1; leftBound--)
            maxTest++;
        for (rightBound = middle+1; rightBound <= end && test(rightBound) == 1; rightBound++)
            maxTest++;
        if (maxTest > max)
            max = maxTest;
    }
    int left = contiguousOnes(begin, leftBound-1, max);
    if (left > max)
        max = left;
    int right = contiguousOnes(rightBound+1, end, max);
    return (left > right ? left : right);
}

bool test(vector <bool>::iterator it)
{
    tests++;
    return *it;
}

Edit: I meant that I used the test() function along with the global tests to count the number of times I tested the value of a bit in the input. I don't know if this was the best way to do so.

[jonnin]

that is pretty cool, and great work.
this is one of those cases where a slick algorithm is slower than brute force for small to modest sized input. At some point the amount of work done by brute force falls behind, but that could literally be a billion bit number here; the computer is stupidly good at iteration and not quite so good at branching and all that. Everyone falls into this trap now and then; I spent a day playing with integer power function trying to beat a dumb loop, and was able to edge it out for powers > 10 or so (but the typical piece of code is doing squares and cubes, and mine was slower or no better (can't recall) for those).

or another way of saying it... lg(n) where every iteration takes 1 second is not as good as n*n where every iteration takes 1 nanosecond, and won't beat that until n becomes rather large.

you can speed it up a bit, of course, if you wanted to play with the code, but that would be tweaking stuff. I don't think there is an algorithmic improvement.

[tpb]

There it is. After virtually no input he's asking you to do even more work for him.